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

· · 题解

退役快乐。

先拆贡献，最后答案为每条边为轻边的概率和子树大小成绩的和。

然后很自然地想到 dp，设 f_{u,i} 表示以 u 为根的子树，根所在重链长度为 i 的概率。

算出这个以后，考虑怎么转移。

我们对于 u 的每个儿子 v，计算出 g_{v,i} 表示以 v 为根的子树，根所在重链长度为 i 且 v 为重儿子的概率。利用 g 我们可以同时更新答案和 f。

考虑计算 g。由于概率与所有 v\in son(u) 的所在重链长度和有关，我们需要完成一个背包问题。直接背包复杂度就是平方的，但是在算 g 时我们需要抛掉 v 子树的贡献。

我们考虑将背包写成函数形式，我们直接背包算的是

H=\prod_{v\in son(u)}\sum_{i=1} f_{v,i}x^i

那么我们考虑如果要撤销 v 的贡献，就需要乘以

\frac {1} {\sum_{i=1}f_{v,i}x^i}

我们考虑找到最小的 j 满足 f_{v,j} 不为 0，于是将撤销的贡献式子变成

\frac{1}{f_{v,j}x^j}\times\frac{1}{1-(\sum_{i=j+1} -\frac{f_{v,i}}{f_{v,j}}x^i)}

我们先处理前面的，只需要朴素的平移。对于后面部分我们有经典的

\frac{1}{1-x}=1+x+x^2+\cdots

背包实现时就是从小到大枚举容量然后再算 v 的每个 i 的贡献，系数就是式子中的 -\frac{f_{v,i}}{f_{v,j}}。

由于我们撤销之后的背包容量的范围是 [0,size_u-size_v]，而 i 的范围是 [1,size_v]，我们不难发现对于整棵树的任意一对点，它们只会在 \text{LCA} 处产生恰好两次贡献，于是背包复杂度为 \mathcal{O}(n^2)。

得到背包后，直接计算 g_{v,i} 和算入贡献是朴素的 \mathcal{O}(n^2)，于是我们就做完了今年的第一题。