FPEvalRepoPublic/LeetCodeMetaData

1{2  "id": 3112,3  "name": "count-valid-paths-in-a-tree",4  "difficulty": "Hard",5  "link": "https://leetcode.com/problems/count-valid-paths-in-a-tree/",6  "date": "2023-09-17",7  "task_description": "There is an undirected tree with `n` nodes labeled from `1` to `n`. You are given the integer `n` and a 2D integer array `edges` of length `n - 1`, where `edges[i] = [ui, vi]` indicates that there is an edge between nodes `ui` and `vi` in the tree. Return _the **number of valid paths** in the tree_. A path `(a, b)` is **valid** if there exists **exactly one** prime number among the node labels in the path from `a` to `b`. **Note** that: The path `(a, b)` is a sequence of **distinct** nodes starting with node `a` and ending with node `b` such that every two adjacent nodes in the sequence share an edge in the tree. Path `(a, b)` and path `(b, a)` are considered the **same** and counted only **once**. **Example 1:** ``` **Input:** n = 5, edges = [[1,2],[1,3],[2,4],[2,5]] **Output:** 4 **Explanation:** The pairs with exactly one prime number on the path between them are: - (1, 2) since the path from 1 to 2 contains prime number 2. - (1, 3) since the path from 1 to 3 contains prime number 3. - (1, 4) since the path from 1 to 4 contains prime number 2. - (2, 4) since the path from 2 to 4 contains prime number 2. It can be shown that there are only 4 valid paths. ``` **Example 2:** ``` **Input:** n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]] **Output:** 6 **Explanation:** The pairs with exactly one prime number on the path between them are: - (1, 2) since the path from 1 to 2 contains prime number 2. - (1, 3) since the path from 1 to 3 contains prime number 3. - (1, 4) since the path from 1 to 4 contains prime number 2. - (1, 6) since the path from 1 to 6 contains prime number 3. - (2, 4) since the path from 2 to 4 contains prime number 2. - (3, 6) since the path from 3 to 6 contains prime number 3. It can be shown that there are only 6 valid paths. ``` **Constraints:** `1 <= n <= 105` `edges.length == n - 1` `edges[i].length == 2` `1 <= ui, vi <= n` The input is generated such that `edges` represent a valid tree.",8  "test_case": [9    {10      "label": "Example 1",11      "input": "n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]",12      "output": "4 "13    },14    {15      "label": "Example 2",16      "input": "n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]",17      "output": "6 "18    }19  ],20  "constraints": [21    "The path (a, b) is a sequence of distinct nodes starting with node a and ending with node b such that every two adjacent nodes in the sequence share an edge in the tree.",22    "Path (a, b) and path (b, a) are considered the same and counted only once.",23    "1 <= n <= 105",24    "edges.length == n - 1",25    "edges[i].length == 2",26    "1 <= ui, vi <= n",27    "The input is generated such that edges represent a valid tree."28  ],29  "python_template": "class Solution(object):\n    def countPaths(self, n, edges):\n        \"\"\"\n        :type n: int\n        :type edges: List[List[int]]\n        :rtype: int\n        \"\"\"\n        ",30  "java_template": "class Solution {\n    public long countPaths(int n, int[][] edges) {\n        \n    }\n}",31  "metadata": {32    "func_name": "countPaths"33  }34}