Count Prime Values in Subtrees
Problem statement
A tree has n nodes numbered 0 to n - 1 and is rooted at node 0. Each edge [u, v] in edges connects u and v; the two ends may be listed in either order. Node i holds the value values[i].
The subtree of a node is the node itself together with all of its descendants. For each query node queries[j], count the nodes in its subtree whose value is a prime number. A prime number is an integer greater than 1 whose only positive divisors are 1 and itself, so 1 is not prime.
Return an array whose j-th entry is the count for queries[j].
Function
countPrimesInSubtrees(n: int, edges: int[][], values: int[], queries: int[]) → int[]Examples
Example 1
n = 5edges = [[0,1],[0,2],[1,3],[1,4]]values = [2,4,3,5,1]queries = [0,1,2,4]return = [3,1,1,0]- Node
0is the root, so its subtree is the whole tree with values2, 4, 3, 5, 1. The primes are2,3and5:3. - The subtree of node
1is nodes1, 3, 4with values4, 5, 1. Only5is prime:1. - The subtree of node
2is just node2with value3:1. - The subtree of node
4is node4with value1, and1is not prime:0.
Example 2
n = 4edges = [[2,0],[3,2],[1,3]]values = [7,11,9,13]queries = [3,2,0]return = [2,2,3]The edges can be listed in either direction. Rooted at 0, the tree is the path 0 - 2 - 3 - 1. The subtree of node 3 holds nodes 3 and 1 (values 13 and 11, both prime): 2. Node 2 adds value 9 = 3 · 3, which is not prime: still 2. Node 0 adds the prime 7: 3.
Example 3
n = 1edges = []values = [1]queries = [0,0]return = [0,0]A single node with value 1. The number 1 is not prime, so both queries answer 0.
Constraints
1 <= n <= 5000edges.length == n - 1, each edge is[u, v]with0 <= u, v < nandu != v, and the edges form a tree.values.length == n1 <= values[i] <= 10^61 <= queries.length <= 50000 <= queries[j] < n