Algorithms
Hard
2867
3112
Count Valid Paths in a Tree
count-valid-paths-in-a-tree
"""
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:

[https://assets.leetcode.com/uploads/2023/08/27/example1.png]

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:

[https://assets.leetcode.com/uploads/2023/08/27/example2.png]

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.
"""
class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        
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:

[https://assets.leetcode.com/uploads/2023/08/27/example1.png]

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:

[https://assets.leetcode.com/uploads/2023/08/27/example2.png]

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.


Please complete the code below to solve above prblem:
```python
class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        
```

my_solution = Solution()

test_input = { "n": 5, "edges": [[1,2],[1,3],[2,4],[2,5]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 6, "edges": [[1,2],[1,3],[2,4],[3,5],[3,6]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 1, "edges": [] }
assert my_solution.countPaths(**test_input) == 0

test_input = { "n": 2, "edges": [[2,1]] }
assert my_solution.countPaths(**test_input) == 1

test_input = { "n": 4, "edges": [[1,2],[4,1],[3,4]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 5, "edges": [[1,3],[4,3],[2,3],[5,2]] }
assert my_solution.countPaths(**test_input) == 3

test_input = { "n": 5, "edges": [[1,5],[2,1],[4,5],[3,2]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 5, "edges": [[2,3],[4,2],[1,3],[5,1]] }
assert my_solution.countPaths(**test_input) == 3

test_input = { "n": 5, "edges": [[4,1],[5,4],[2,1],[3,4]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 5, "edges": [[3,5],[1,5],[4,3],[2,5]] }
assert my_solution.countPaths(**test_input) == 2

test_input = { "n": 4, "edges": [[2,1],[4,2],[3,2]] }
assert my_solution.countPaths(**test_input) == 3

test_input = { "n": 5, "edges": [[1,4],[2,4],[3,2],[5,4]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 5, "edges": [[5,4],[3,4],[1,4],[2,4]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 4, "edges": [[3,4],[1,3],[2,4]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 10, "edges": [[10,9],[2,10],[1,10],[3,2],[6,10],[4,3],[8,6],[5,8],[7,6]] }
assert my_solution.countPaths(**test_input) == 16

test_input = { "n": 8, "edges": [[7,2],[6,2],[5,2],[1,2],[4,7],[8,1],[3,6]] }
assert my_solution.countPaths(**test_input) == 7

test_input = { "n": 5, "edges": [[3,2],[4,3],[5,4],[1,4]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 9, "edges": [[7,4],[3,4],[5,4],[1,5],[6,4],[9,5],[8,7],[2,8]] }
assert my_solution.countPaths(**test_input) == 17

test_input = { "n": 9, "edges": [[1,8],[5,8],[4,8],[6,5],[3,1],[9,1],[7,4],[2,8]] }
assert my_solution.countPaths(**test_input) == 21

test_input = { "n": 10, "edges": [[2,9],[7,2],[10,9],[5,7],[4,5],[6,7],[8,2],[1,5],[3,10]] }
assert my_solution.countPaths(**test_input) == 11

test_input = { "n": 8, "edges": [[6,1],[8,1],[3,6],[4,1],[7,3],[2,8],[5,1]] }
assert my_solution.countPaths(**test_input) == 12

test_input = { "n": 10, "edges": [[9,1],[8,9],[5,9],[10,8],[7,5],[2,8],[3,8],[6,7],[4,1]] }
assert my_solution.countPaths(**test_input) == 16

test_input = { "n": 5, "edges": [[5,3],[4,5],[2,5],[1,4]] }
assert my_solution.countPaths(**test_input) == 2

test_input = { "n": 7, "edges": [[7,6],[2,6],[5,2],[3,5],[4,5],[1,6]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 8, "edges": [[4,5],[8,4],[6,4],[2,5],[1,6],[3,1],[7,8]] }
assert my_solution.countPaths(**test_input) == 12

test_input = { "n": 10, "edges": [[9,6],[5,6],[10,6],[8,5],[4,8],[3,9],[1,3],[2,6],[7,1]] }
assert my_solution.countPaths(**test_input) == 22

test_input = { "n": 5, "edges": [[1,4],[2,4],[5,4],[3,4]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 10, "edges": [[9,4],[7,9],[10,9],[6,7],[8,7],[2,7],[3,2],[1,9],[5,10]] }
assert my_solution.countPaths(**test_input) == 19

test_input = { "n": 7, "edges": [[4,7],[6,7],[1,7],[3,7],[2,6],[5,6]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 5, "edges": [[1,4],[2,1],[5,2],[3,1]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 5, "edges": [[4,5],[2,5],[1,4],[3,1]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 10, "edges": [[4,3],[5,3],[1,4],[7,5],[6,3],[8,3],[9,1],[10,8],[2,10]] }
assert my_solution.countPaths(**test_input) == 19

test_input = { "n": 5, "edges": [[1,3],[4,1],[2,1],[5,1]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 7, "edges": [[5,2],[3,5],[4,5],[1,2],[6,2],[7,2]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 5, "edges": [[3,4],[1,4],[5,3],[2,5]] }
assert my_solution.countPaths(**test_input) == 2

test_input = { "n": 8, "edges": [[1,8],[2,1],[6,8],[3,6],[4,3],[5,8],[7,2]] }
assert my_solution.countPaths(**test_input) == 13

test_input = { "n": 9, "edges": [[2,1],[6,1],[8,2],[9,8],[4,9],[7,9],[3,1],[5,2]] }
assert my_solution.countPaths(**test_input) == 16

test_input = { "n": 5, "edges": [[4,3],[5,4],[1,5],[2,3]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 8, "edges": [[2,4],[3,4],[6,4],[7,3],[8,7],[5,6],[1,5]] }
assert my_solution.countPaths(**test_input) == 10

test_input = { "n": 6, "edges": [[3,6],[1,3],[2,3],[5,2],[4,5]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 10, "edges": [[7,5],[4,7],[10,5],[6,5],[8,6],[2,8],[9,4],[3,10],[1,9]] }
assert my_solution.countPaths(**test_input) == 11

test_input = { "n": 8, "edges": [[3,2],[8,3],[7,3],[6,2],[4,7],[5,6],[1,8]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 8, "edges": [[2,6],[3,6],[5,2],[1,6],[7,2],[8,1],[4,1]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 9, "edges": [[3,7],[6,7],[4,7],[1,6],[8,4],[9,1],[2,7],[5,2]] }
assert my_solution.countPaths(**test_input) == 11

test_input = { "n": 6, "edges": [[6,2],[5,6],[1,2],[3,2],[4,3]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 6, "edges": [[6,2],[1,6],[3,1],[5,3],[4,3]] }
assert my_solution.countPaths(**test_input) == 7

test_input = { "n": 8, "edges": [[2,3],[8,3],[5,3],[6,3],[4,3],[7,8],[1,2]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 7, "edges": [[4,6],[5,6],[7,6],[3,4],[2,6],[1,5]] }
assert my_solution.countPaths(**test_input) == 11

test_input = { "n": 6, "edges": [[4,2],[5,4],[1,5],[6,1],[3,1]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 6, "edges": [[4,1],[6,1],[5,4],[3,5],[2,1]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 7, "edges": [[6,7],[1,6],[4,6],[2,7],[3,2],[5,7]] }
assert my_solution.countPaths(**test_input) == 3

test_input = { "n": 6, "edges": [[4,3],[5,3],[6,5],[2,4],[1,5]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 10, "edges": [[2,5],[3,5],[10,2],[8,3],[7,5],[4,3],[1,8],[9,5],[6,8]] }
assert my_solution.countPaths(**test_input) == 9

test_input = { "n": 8, "edges": [[2,8],[1,8],[5,2],[4,5],[6,5],[7,2],[3,5]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 8, "edges": [[7,2],[6,7],[5,7],[8,6],[1,7],[3,5],[4,2]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 7, "edges": [[5,7],[3,5],[2,7],[4,3],[6,3],[1,4]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 7, "edges": [[2,3],[1,3],[7,3],[4,1],[6,3],[5,1]] }
assert my_solution.countPaths(**test_input) == 7

test_input = { "n": 7, "edges": [[4,2],[6,4],[1,6],[7,6],[5,2],[3,7]] }
assert my_solution.countPaths(**test_input) == 6

test_input = { "n": 6, "edges": [[3,4],[6,3],[1,4],[5,4],[2,6]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 10, "edges": [[2,7],[1,2],[8,7],[4,2],[6,8],[10,7],[5,4],[9,8],[3,6]] }
assert my_solution.countPaths(**test_input) == 14

test_input = { "n": 8, "edges": [[6,2],[7,2],[5,6],[8,2],[3,6],[1,8],[4,2]] }
assert my_solution.countPaths(**test_input) == 11

test_input = { "n": 10, "edges": [[9,6],[1,9],[2,1],[8,1],[10,6],[7,6],[3,8],[4,3],[5,3]] }
assert my_solution.countPaths(**test_input) == 21

test_input = { "n": 8, "edges": [[4,6],[1,6],[7,6],[2,1],[8,7],[5,6],[3,5]] }
assert my_solution.countPaths(**test_input) == 13

test_input = { "n": 7, "edges": [[3,7],[6,7],[4,6],[1,3],[5,3],[2,3]] }
assert my_solution.countPaths(**test_input) == 3

test_input = { "n": 10, "edges": [[2,9],[3,9],[8,9],[10,3],[1,9],[4,8],[7,10],[6,1],[5,10]] }
assert my_solution.countPaths(**test_input) == 18

test_input = { "n": 8, "edges": [[5,6],[3,6],[7,5],[4,6],[8,6],[2,3],[1,3]] }
assert my_solution.countPaths(**test_input) == 10

test_input = { "n": 9, "edges": [[9,3],[4,3],[2,9],[7,3],[8,7],[1,7],[5,4],[6,2]] }
assert my_solution.countPaths(**test_input) == 10

test_input = { "n": 6, "edges": [[5,1],[2,1],[4,2],[6,5],[3,4]] }
assert my_solution.countPaths(**test_input) == 7

test_input = { "n": 7, "edges": [[3,6],[2,6],[5,6],[7,2],[1,6],[4,2]] }
assert my_solution.countPaths(**test_input) == 9

test_input = { "n": 5, "edges": [[1,5],[3,5],[4,3],[2,5]] }
assert my_solution.countPaths(**test_input) == 2

test_input = { "n": 8, "edges": [[2,8],[6,2],[1,2],[4,1],[7,2],[3,2],[5,7]] }
assert my_solution.countPaths(**test_input) == 9

test_input = { "n": 9, "edges": [[5,3],[1,3],[7,3],[4,5],[6,7],[8,7],[9,5],[2,5]] }
assert my_solution.countPaths(**test_input) == 7

test_input = { "n": 10, "edges": [[8,10],[3,10],[1,8],[7,8],[6,10],[2,3],[5,8],[9,5],[4,6]] }
assert my_solution.countPaths(**test_input) == 21

test_input = { "n": 10, "edges": [[4,8],[6,8],[9,4],[1,6],[5,8],[2,8],[10,9],[7,6],[3,5]] }
assert my_solution.countPaths(**test_input) == 18

test_input = { "n": 9, "edges": [[4,6],[9,4],[3,6],[7,6],[1,4],[5,9],[2,7],[8,4]] }
assert my_solution.countPaths(**test_input) == 15

test_input = { "n": 7, "edges": [[7,6],[2,6],[1,7],[3,2],[5,2],[4,5]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 9, "edges": [[1,8],[5,8],[3,8],[2,1],[9,2],[7,1],[6,5],[4,9]] }
assert my_solution.countPaths(**test_input) == 17

test_input = { "n": 7, "edges": [[3,5],[4,3],[6,5],[2,4],[7,3],[1,4]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 10, "edges": [[5,2],[8,5],[10,5],[3,8],[4,2],[1,4],[9,10],[7,5],[6,8]] }
assert my_solution.countPaths(**test_input) == 12

test_input = { "n": 8, "edges": [[7,4],[1,4],[5,7],[6,1],[8,5],[3,8],[2,6]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 10, "edges": [[8,2],[7,8],[9,2],[4,2],[6,4],[3,9],[5,4],[1,9],[10,8]] }
assert my_solution.countPaths(**test_input) == 24

test_input = { "n": 8, "edges": [[3,8],[2,8],[1,8],[6,8],[4,3],[7,6],[5,2]] }
assert my_solution.countPaths(**test_input) == 13

test_input = { "n": 9, "edges": [[5,4],[2,4],[9,5],[3,2],[7,3],[1,4],[8,2],[6,4]] }
assert my_solution.countPaths(**test_input) == 14

test_input = { "n": 10, "edges": [[10,8],[5,10],[1,10],[3,10],[7,3],[2,10],[6,8],[9,6],[4,6]] }
assert my_solution.countPaths(**test_input) == 18

test_input = { "n": 9, "edges": [[6,7],[5,7],[8,7],[9,6],[2,5],[4,5],[1,8],[3,6]] }
assert my_solution.countPaths(**test_input) == 11

test_input = { "n": 10, "edges": [[1,6],[9,1],[5,9],[10,6],[4,9],[8,9],[7,8],[2,1],[3,1]] }
assert my_solution.countPaths(**test_input) == 24

test_input = { "n": 8, "edges": [[4,5],[3,4],[6,5],[1,4],[2,3],[8,4],[7,3]] }
assert my_solution.countPaths(**test_input) == 10

test_input = { "n": 7, "edges": [[7,4],[6,4],[2,6],[5,6],[3,2],[1,5]] }
assert my_solution.countPaths(**test_input) == 9

test_input = { "n": 10, "edges": [[3,2],[5,3],[1,2],[9,5],[7,5],[6,3],[4,3],[8,6],[10,1]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 8, "edges": [[2,8],[5,2],[4,2],[7,4],[3,2],[1,3],[6,3]] }
assert my_solution.countPaths(**test_input) == 7

test_input = { "n": 6, "edges": [[6,3],[2,3],[4,2],[5,2],[1,6]] }
assert my_solution.countPaths(**test_input) == 3

test_input = { "n": 9, "edges": [[7,3],[5,3],[4,3],[9,7],[6,5],[8,3],[2,4],[1,5]] }
assert my_solution.countPaths(**test_input) == 8

test_input = { "n": 5, "edges": [[1,2],[5,1],[4,5],[3,4]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 9, "edges": [[8,3],[6,8],[2,8],[4,3],[5,4],[7,5],[9,4],[1,5]] }
assert my_solution.countPaths(**test_input) == 15

test_input = { "n": 5, "edges": [[2,1],[4,2],[5,1],[3,2]] }
assert my_solution.countPaths(**test_input) == 4

test_input = { "n": 6, "edges": [[4,2],[6,2],[3,2],[1,6],[5,2]] }
assert my_solution.countPaths(**test_input) == 5

test_input = { "n": 10, "edges": [[10,5],[3,10],[4,3],[8,3],[7,4],[1,7],[6,5],[9,1],[2,5]] }
assert my_solution.countPaths(**test_input) == 14

test_input = { "n": 9, "edges": [[4,7],[6,4],[8,4],[2,8],[5,2],[9,7],[1,6],[3,7]] }
assert my_solution.countPaths(**test_input) == 13

test_input = { "n": 10, "edges": [[7,3],[1,3],[2,3],[10,2],[4,2],[8,1],[9,4],[5,3],[6,3]] }
assert my_solution.countPaths(**test_input) == 10

test_input = { "n": 7, "edges": [[4,7],[2,7],[3,4],[1,7],[6,4],[5,4]] }
assert my_solution.countPaths(**test_input) == 9