题解：P15649 [省选联考 2026] 找寻者 / recollector

· · 题解

省选竟然考期望了。

首先考虑 DP。

先把问题转化，就是问每条边轻的概率，你需要输出它们乘上子树大小的结果。

直接做做不了一点。

考虑最难的是 \frac{l_i}{\sum l_j}。

我们可以设 dp_{i,j} 表示 i 子树里，重链长为 j 的概率。

考虑计算重边概率怎么算？

把所有其它边上的儿子的 dp 卷积合起来，然后和这个枚举算概率。

直接做一个节点就是 O(n^3) 了，过不去。

考虑优化，看似正确的前后缀背包合并，发现每次还是得卷，复杂度爆炸。

考虑先全乘起来再分别除，两个长分别 a,b 的多项式相除复杂度为 O(ab)。

算 t 单个儿子 v 复杂度 O(sz_tsz_v)，加起来是 O({sz_t}^2)，单点是对的。

整体呢？

考虑点对在哪里贡献。

发现必须在最近公共祖先处一个在长链上，一个恰好走第一次轻边才在乘法和除法分别做一次贡献。

复杂度 O(n^2)。

代码出了再发，希望别挂，也祝各位不挂分，暴力能过。