883. Prime Paths in a Tree
A courier network is a tree of n depots numbered 1 to n; edges[i] = [a, b] joins depots a and b by a two-way road. A depot is special when its number is a prime (1 is not prime).
Count the unordered pairs of different depots {u, v} whose unique road path (both end depots included) passes through exactly one special depot. Paths u-v and v-u count once, and a path of a single depot is not counted. Return the count as a long; it never exceeds about n * n / 2.
Example 1
- Input:
- n = 5, edges = [[1,4],[4,2],[2,3],[3,5]]
- Output:
- 2
- Explanation:
The line 1-4-2-3-5 holds primes 2, 3 and 5; only the paths 4-2 and 1-4-2 contain exactly one prime, and every other path through 2, 3 or 5 meets a second prime.
Example 2
- Input:
- n = 7, edges = [[1,2],[2,3],[2,4],[4,5],[4,6],[6,7]]
- Output:
- 9
- Explanation:
Prime 2 is the only prime on 5 paths (2-1, 2-4, 2-4-6, 1-2-4, 1-2-4-6), prime 5 on 2 (5-4, 5-4-6), prime 7 on 2 (7-6, 7-6-4) and prime 3 on none, so 5 + 2 + 2 = 9.
Constraints
- 1 ≤ n ≤ 105
edges.length = n - 1; the edges form a tree on depots 1..n- 1 ≤ a, b ≤ n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n * alpha(n))
- Space
- O(n)