题目大意
$n$ 个点的树，进行点分，每次随机选择分治中心，求期望复杂度。
例如长度为 $3$ 的链，期望复杂度是 $\frac{2}{3}(3+(2+1))+\frac{1}{3}(3+(1+1))=\frac{17}{3}$
$n \le 30000$
题解
有点妙。。。
考虑每个点的贡献，其实就是它在点分树上的期望深度。
也就是其他点成为它点分树祖先的概率和。
考虑两个点 $i$ 和 $j$，$j$ 成为 $i$ 的祖先，当且仅当 $i$ 到 $j$ 的路径上，第一个被分治的是 $j$。
因此期望复杂度是：
考虑用点分来求这个东西。
对于当前子树，可以求出 $d[i]$ 表示到根距离为 $i$ 的路径数量。然后 $d$ 数组自己卷积一下就可以得到长度为 $i$ 的路径数量。
因为 $d$ 的元素大小随分治而减小，所以点分+FFT的总时间是 $T(n)=O(n~log~n)+2T(\frac{n}{2})=O(n \log^2 n)$