开个新坑，系列名叫“引爆逆天力量，追寻圆环之理的神藏奥秘”（来源：ChatGPT3.5)。

对于树上所有两点距离的问题，考虑点分治。记当前分治中心为 $C$，对于在分治范围内的点 $u$，考虑计算所有经过 $C$ 的路径对 $u$ 的贡献。记 $f_i$ 表示与 $C$ 距离为 $i$ 的点的个数，若 $u$ 与 $C$ 的距离为 $d$，那么对 $u$ 的贡献为

$$\Delta_u=\sum_{i=0}^{D}{f_i w_{i+d}}$$

其中 $D$ 为分治范围到 $C$ 的最大距离。注意到这是一个差卷积的形式，处理方式是将 $f$ 倒置，即 $f'_i=f_{D-i}$，那么有

$$\Delta_u=\sum_{i=0}^{D}{f'_{D-i} w_{i+d}}=[x^{D+d}](\sum_{i}{f'_i x^i})(\sum_{i}{w_i x^i})$$

使用 NTT 计算卷积即可。然后再类似的减去 $u$ 所属子树对它的贡献。

注意到卷积只用计算前 $2D$ 位，这样就可以保证复杂度为 $O(n\log^2 n)$。以及答案最大 $1e9$，NTT 质数可以取 $1004535809$，原根为 $3$。