题解：P15649

Danslapiscine · 2026-03-07 15:57:47 · 题解

非常直接。

直接做，将答案拆成每条边的贡献。设点 i 的重链长度为 j 的概率为 p_{i,j}。那么去枚举每个点，去计算从该点出发的边的贡献。贡献为：\sum_x \dfrac{ \sum_{i是儿子节点} x_isiz_i \prod_{i是儿子节点} p_{i,x_i}}{\sum x}。用 dp 计算它，维护 g_i 表示目前 \sum x=i 的贡献和。计算辅助数组 f_i 表示目前 \sum_{\sum x=i}\prod p_{j,x_j} 的值。利用树形背包就能做到 O(n^2)。

现在考虑怎样得到 p。我们考虑钦定该节点 pos 其中一个儿子 v 的重链长度为 len，其他儿子重链长度之和为 S。那么它就会对 p_{pos,len+1} 产生贡献。贡献为 p_{v,len}\dfrac{len}{S+len} 乘上其他儿子重链长度和为 S 的概率，怎么算呢？设该概率为 f_S^’，有 f_i=\sum f_j^’p_{v,i-j}，解方程即可。时间复杂度是 O(siz_v(siz_{pos}-siz_v))。我们枚举 len 和 S 的复杂度为 O(n^2)，解方程的复杂度是O(siz_{pos}^2 - \sum siz_v^2)，加起来就是 O(n^2) 的。