场上被这道题送走了。

直接做显然是很困难的，不过根据期望的性质，我们可以把答案的贡献拆到每一个子树上，具体的，对于一个大小为 $siz_x$ 的子树 $x$，若 $(x,fa_x)$ 成为重边的概率为 $P$，则这个子树对答案的贡献为 $(1-P)siz_x$。

接下来就是求出 $P=\frac{l_i}{\sum_{j=1}^k l_j}$ 了，显然我们可以在树上做 dp，并分别记录 $f_{i,j}$ 表示 $i$ 下有一条长度为 $j$ 重链的概率，$g_{i,j}$ 表示 $i$ 所有儿子重链长度之和为 $j$ 的概率。

$g_{i,j}$ 的转移是一个树上背包状物，不断让 $g,f$ 卷积即可，根据经典结论，树上背包的时间复杂度由每个点对贡献得来，复杂度为 $O(n^2)$。

$f_{i,j}$ 的计算和 $P$ 的计算是一体的，考虑 $x$ 的重链从他的儿子 $y$ 继承。枚举重链长度 $i$，则 $f_{x,i+1}\gets \sum_{j}f_{y,i}\times h_{x,j}\times \frac{i}{i+j}$，其中 $h_{x,j}$ 表示 $g_{x,j}$ 在不考虑 $y$ 这个儿子的情况下的背包数组。

$f_{i,j}$ 的计算可以通过预处理所有儿子实际上的长链之和，用树上背包的方法做到 $O(n^2)$，逆元直接预处理 $1\sim n$ 的即可。问题在于如何快速求 $h$。

方法一：记录 $v_1,v_2,\dots,v_k$ 的前缀背包和后缀背包，求 $h$ 只需要暴力卷积前后缀即可，复杂度为 $O(n^3)$。

方法二：考虑优化上面的过程，用 NTT 算法做卷积，时间复杂度为 $O(n^2\log n)$。

方法三：考虑分治算法，设分治到区间 $[l,r]$ 表示不考虑区间 $[l,r]$ 内所有元素时的 $h$，如果要分治处理 $[l,mid]$ 就将 $[mid+1,r]$ 的信息加到 $h$ 上，再丢到 $[l,mid]$ 处理，$[mid+1,r]$ 同样如此，常数较小，时间复杂度为 $O(n^2\log n)$。

方法四：上述三种算法都将除法变成乘法处理，考虑直接用除法，用 $g_x$ 除去 $f_y$。对于两个多项式 $F,G$（$F$ 为 $G$ 的倍数），他们的次数分别是 $l_1,l_2$（$l_1>l_2$），则 $\frac{F}{G}$ 的次数为 $l_1-l_2$，可以模拟竖式除法的过程，暴力除法的时间复杂度为 $l_2(l_1-l_2)$。不难发现，这个形式也及其类似树上背包的时间复杂度分析（每个点对会贡献一次），所以直接暴力除就可以了，每次只需要对 $f_y$ 的最高次项求逆元即可。时间复杂度为 $O(n^2)$。

此时，就解决了这道题目的所有问题，做到了 $O(n^2)$ 的时间复杂度。官方数据疑似放了很多 $O(n^3),O(n^2\log n)$ 的解法过去（后者几乎全过了）。