题意

求给定的 $n$ 个点的基环树点对最短距离的 $k$ 次方的期望。

限制

$1\le n\le 10^5,1\le k\le 10^9$。

题解

由于 $k$ 太大，此时 $d(u,v)^k$ 并没有能够快速合并的方法，于是问题转化为对每个 $i$ 求 $d(u,v)=i$ 的点对数量。

首先在环上的同一棵子树内的答案可以直接使用点分治和 FFT 解决，时间复杂度 $O(n(\log n)^2)$。

现在考虑不同子树的贡献。设环长为 $l$，$m:=\lfloor\frac{l}2\rfloor$，环上的点依次为 $0,1,\ldots,l-1$。

首先可以分治 FFT 求出 $[0,m)$ 和 $[m,2m)$ 内部的贡献，如果 $l\bmod 2=1$，再额外加上所有点与最后一个点的贡献。

现在问题转化为求 $[0,m)$ 和 $[m,2m)$ 之间的贡献。

对于 $i\in[0,m)$，可以发现：

1. 当 $0\le j< i$ 时，$i$ 和 $j+m$ 之间的距离为 $j+m-i$；
2. 当 $i=j$ 时，$i$ 和 $j+m$ 之间的距离为 $m$；
3. 当 $i< j< m$ 时，$i$ 和 $j+m$ 之间的距离为 $l-j-m+i$。

于是问题又变成了 $[0,m)$ 内部两两之间的贡献，同样可以分治 FFT 解决，需要单独处理情况 2。

这里的分治 FFT 的每一项都是多项式，但每个多项式只会对 $O(\log n)$ 层有贡献，且多项式的总长度为 $O(n)$，所以总时间复杂度为 $O(n(\log n)^2)$。