# [Solution] Count Valid Paths in a Tree Solution Leetcode

### 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] = [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 ```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: Count Valid Paths in a Tree Solution Leetcode ```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: Count Valid Paths in a Tree Solution Leetcode

• `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.

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:

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

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