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

shinzAnmono · 2026-03-07 14:46:39 · 题解

这题不卡三次方我建议评黄。。。

先拆期望贡献，答案是每条边作为轻边的概率和子树大小的乘积的和。

设 p_{u,l} 表示节点 u 在长度为 l 的重链的概率，对于每条边 fa_v\rightarrow v，我们计算他为重边的概率。

设 g_{v,l} 表示 v 的兄弟所在重链长度和为 l 的概率,则 P=\sum g_{v,i}p_{v,j}\frac{j}{i+j}，直接求是 O(n^3) 的，无法通过。

记 f_{u,l} 表示 u 的所有子节点所在的重链长度和为 l 的概率，这个可以树上背包做到平方。则 f_{u,i+j}=\displaystyle\sum_{i+j\leq size_u} g_{v,i}p_{v,j}。将 g 视为未知量，这是一个方程组。

发现 p_{v,l} 不可能全为 0，记第一个非零的为 p_{v,k}。则 g_{v,i}=\displaystyle\frac{f_{u,i+k}-\sum_{k<j\leq i+k-1}g_{v,i+k-j}p_{v,j}}{p_{v,k}}，这样可以做到平方，后续可转移 p 及求出答案。

P.S. 求解的时候，可以先处理逆元，这样就可以做到不带 log。

代码发下来放。