# 描述

You are given a tree. If we select 2 distinct nodes uniformly at random, what’s the probability that the distance between these 2 nodes is a prime number?

## Input

The first line contains a number $N$: the number of nodes in this tree.
The following $N-1$ lines contain pairs $a[i]$ and $b[i]$, which means there is an edge with length $1$ between $a[i]$ and $b[i]$.

## Output

Output a real number denote the probability we want.
You’ll get accept if the difference between your answer and standard answer is no more than $10^{-6}$.

## Constraints

$2 ≤ N ≤ 50,000$

The input must be a tree.

## Explanation

We have $C(5, 2) = 10$ choices, and these 5 of them have a prime distance:

$1-3, 2-4, 3-5: 2$

$1-4, 2-5: 3$

Note that $1$ is not a prime number.

# 思路

• 树上路径统计问题的经典套路就是点分治，然后统计每个点的路径条数。
• 对于每个结点的所有孩子计算到根的距离，用FFT求卷积，枚举素数统计答案即可。
• 同时会计算来自同一儿子结点的子树中两个结点的路径，需要把这个情况的答案减去。
• 具体实现看代码～

0%