### 2867. Count Valid Paths in a Tree Solution Leetcode

**User Accepted:**513**User Tried:**1524**Total Accepted:**560**Total Submissions:**3494**Difficulty:**Hard

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] = [u`

indicates that there is an edge between nodes _{i}, v_{i}]`u`

and _{i}`v`

in the tree._{i}

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**

Input:n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]Output:4Explanation: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: Count Valid Paths in a Tree Solution Leetcode**

Input:n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]Output:6Explanation: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: Count Valid Paths in a Tree Solution Leetcode**

`1 <= n <= 10`

^{5}`edges.length == n - 1`

`edges[i].length == 2`

`1 <= u`

_{i}, v_{i}<= n- The input is generated such that
`edges`

represent a valid tree.

** Solution**

**Count Valid Paths in a Tree Solution Leetcode**

import math

def countValidPaths(n, edges):

# Create an adjacency list to represent the tree

adj_list = [[] for _ in range(n)]

for u, v in edges:

adj_list[u – 1].append(v – 1)

adj_list[v – 1].append(u – 1)

def is_prime(num):

if num < 2:

return False

for i in range(2, int(math.sqrt(num)) + 1):

if num % i == 0:

return False

return True

def dfs(node, parent):

nonlocal valid_paths

prime_count = 0

for neighbor in adj_list[node]:

if neighbor == parent:

continue

prime_count += dfs(neighbor, node)

prime_count += is_prime(node + 1)

if prime_count == 1:

valid_paths += 1

return prime_count

valid_paths = 0

dfs(0, -1) # Start DFS from the root node (node 1)

return valid_paths

# Example 1

n1 = 5

edges1 = [[1, 2], [1, 3], [2, 4], [2, 5]]

print(countValidPaths(n1, edges1)) # Output: 4

# Example 2

n2 = 6

edges2 = [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]]

print(countValidPaths(n2, edges2)) # Output: 6