Use the sieve of Eratosthenes to find all prime numbers in the range [1, n].****
提示 2
Root the tree at any node.
提示 3
Let dp[i][0] = the number of vertical paths starting from i containing no prime nodes , and dp[i][1] = the number of vertical paths starting from i containing one prime node .
提示 4
If i is not prime, dp[i][0] = sum(dp[child][0]) + 1, and dp[i][1] = sum(dp[child][1]) for each child of i in the rooted tree.
提示 5
If i is prime, dp[i][0] = 0, and dp[i][1] = sum(dp[child][0]) + 1 for each child of i in the rooted tree.
提示 6
For each node i, and using the computed dp matrix, count the number of unordered pairs (a,b) such that lca(a,b) = i, and there exists exactly one prime number on the path from a to b.
