Description：

$n-1$ 次操作，每次随机删掉一条边，一个联通块的价值是这个联通块的大小的平方，对于每一天求期望价值和。

$1\leqslant n\leqslant10^5$

Solution：

遇到这种平方的题，一个很妙的转化就是我们可以考虑每一对点对答案的贡献，他们对第 $i$ 天的贡献是： $$ \frac{(n-1-dis(i,j))^{\underline i}}{(n-1)^{\underline i}} $$ 那么： $$ ans[i]=\sum_{d=0}^{n-1}cnt[d]\times \frac{(n-1-d)^{\underline i}}{(n-1)^{\underline i}}=\sum_{d=0}^{n-1}cnt[d]\times \frac{(n-1-d)!(n-1-i)!}{(n-1-d-i)!(n-1)!} $$ 设 $val[i]=(n-1-i)!$ ，那么： $$ ans[i]=\frac{val[i]}{(n-1)!}\sum_{d=0}^{n-1}\frac{cnt[d]val[d]}{val[d+i]} $$

后面显然是一个卷积，那么我们可以先用 $FFT$ 求出树上长度为 $i$ 的路径条数，然后最后再用任意模数 $FFT$ 算那个式子。

Code：

没有代码