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

Eric998 · 2026-03-07 18:08:03 · 题解

考虑这样一个事实：一个点走到 1 经过的轻边数是它作为轻儿子的祖先数。因此求出每个点 u 被选的概率 p，其对答案的贡献即为 (1-p)sz_u。

设 dp_{i,j} 为 i 向下的重链长度为 j 的概率，转移考虑枚举 u 的重儿子 v 及其重链长 l，则需要求出其他所有儿子重链长和为 s 的概率 p_s，转移 dp_{u,l+1}\leftarrow dp_{v,l}\times \frac l{l+s}\times p_s。