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:
(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.(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 <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= nedges represent a valid tree.#2867 Count Valid Paths in a Tree combines ideas from tree traversal, number theory, and combinatorics. The key observation is that a valid path must contain exactly one prime-numbered node. Instead of checking every possible path, which would be too slow, we can analyze how prime nodes connect different groups of non-prime nodes.
First, use a sieve of Eratosthenes to precompute which node values are prime. Then build an adjacency list for the tree and use DFS to identify connected components consisting only of non-prime nodes. For each prime node, examine its neighboring non-prime components and count how many paths can be formed that include this prime as the only prime in the path. By combining component sizes mathematically, we can efficiently count valid paths.
This approach avoids enumerating all paths and leverages tree structure properties to achieve near-linear performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sieve + DFS with component counting | O(n + n log log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use the sieve of Eratosthenes to find all prime numbers in the range <code>[1, n]</code>.****
Root the tree at any node.
Let <code>dp[i][0] = the number of vertical paths starting from i containing no prime nodes </code>, and <code>dp[i][1] = the number of vertical paths starting from i containing one prime node </code>.
If <code>i</code> is not prime, <code>dp[i][0] = sum(dp[child][0]) + 1</code>, and <code>dp[i][1] = sum(dp[child][1])</code> for each <code>child</code> of <code>i</code> in the rooted tree.
If <code>i</code> is prime, <code>dp[i][0] = 0</code>, and <code>dp[i][1] = sum(dp[child][0]) + 1</code> for each <code>child</code> of <code>i</code> in the rooted tree.
For each node <code>i</code>, and using the computed <code>dp</code> matrix, count the number of unordered pairs <code>(a,b)</code> such that <code>lca(a,b) = i</code>, and there exists exactly one prime number on the path from <code>a</code> to <code>b</code>.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems combining tree traversal with mathematical observations and counting techniques are common in FAANG-style interviews. This problem tests DFS, graph reasoning, and the ability to convert path enumeration into a combinatorial counting problem.
Number theory is used to determine which nodes are prime. Since a valid path must contain exactly one prime node, efficiently identifying primes using a sieve helps reduce repeated prime checks during traversal.
An adjacency list is the best structure for representing the tree because it enables efficient DFS traversal. Additional arrays or lists are used to track prime numbers and the sizes of non-prime connected components.
The optimal approach uses a combination of the Sieve of Eratosthenes, DFS, and component counting. By grouping connected non-prime nodes and evaluating paths through each prime node, we can count valid paths efficiently without enumerating all pairs.