【bzoj3451】【Tyvj1953】Normal 题解

题目大意

  $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$。
  因此期望复杂度是：

$$\sum_{i=1}^n\sum_{j=1,j≠i}^n\frac{1}{dis(i,j)}$$

  考虑用点分来求这个东西。
  对于当前子树，可以求出 $d[i]$ 表示到根距离为 $i$ 的路径数量。然后 $d$ 数组自己卷积一下就可以得到长度为 $i$ 的路径数量。
  因为 $d$ 的元素大小随分治而减小，所以点分+FFT的总时间是 $T(n)=O(n~log~n)+2T(\frac{n}{2})=O(n \log^2 n)$