BZOJ3451NORMAL

题目传送门

考虑每个点对的贡献。

对于(x,y),如果x对y有1的贡献(即y在点分树上是x的祖先),那么y一定是x到y路径上第一个被选做分治中心的点。

一条路径上被选择的点概率相等,因此贡献为

所以答案就是

原问题就转化为了点分治的基础问题。

点分治,处理出当前点分树上的所有深度。

上面这个东西是一个很舒服的卷积。

FFT即可。

主要是来填一下点分治的坑。

将原树问题拆分成两个子树问题分治

比如求上面这个东西,你直接FFT的话会出现子树之内重复统计,就要减去子树内的贡献。

类似差分。