[Solution] Count Valid Paths in a Tree Solution Leetcode

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