题解：P15649 [省选联考 2026] 找寻者 / recollector
MoLing_qwq
·
·
题解
recallector
期望有线性性。考虑算每条边的贡献。
设 siz_i 为子树大小，son_i 为儿子集合。考虑 DP，定义 p_{i,L} 表示 i 所在重链长度为 L 的概率，e_{i,L} 表示 i 所在重链长度为 L 时 i\to fa_i 是重边的概率。
转移需要考虑子节点重链长度和，只能背包。对于 i 的子节点 s，求出除 s 以外的所有子节点，所在重链长度和为 L 的概率，就可以用 p_{i,L} 算 e_{i,L} 了。然而除 s 以外的限制很恶心，背包怎么带删除呢？
考虑这里的背包可以写成概率生成函数。定义随机变量 p 的概率生成函数（PGF）F(p)=\sum a_ix^i，表示 p 有 a_i 的概率为 i。背包合并就是 PGF 乘法，删除单点就是 PGF 除法。令 F(i)=\sum_L p_{i,L}x^L，M(i)=\prod_{j\in son_i}F(j)，我们需要求 \frac{M(i)}{F(j)}，其中 j\in son_i。
直接暴力作多项式除法，我们证明，这样的时间复杂度为 \bold{O(n^2)}。
对每个点 i，求 M(i) 是标准的树上背包，复杂度 O(n^2)。考虑除法部分，n 次多项式除以 m 次多项式的复杂度可以做到 O(m(n-m))。设点 i 的子节点为 s_1,s_2,\dots,s_k，F(s_i) 的次数为 a_1,a_2,\dots,a_k。
则 M(i) 的次数为 \sum a_i。M(i) 除以 F(s_t) 的复杂度为 O(a_t(\sum a_i-a_t))=O(a_t\sum_{x\neq t}a_x)，对所有 t 求和得 \sum_{x\neq y}a_xa_y。由于 a_t\le siz_{s_t}，这部分时间复杂度和一般的树上背包一样，也为 O(n^2)。
这样我们在合理的时间内求出了 e_{i,L}。接下来要求 p_{i,L}，这很简单，对于所有 i 的儿子 j，对每个 L，p_{j,L}e_{j,L} 对 p_{i,L+1} 造成贡献。边界是叶子的 p_{i,0}=1。注意转移顺序。
最后，每条边成为轻边，会导致子树内所有点到根的轻边数量 +1。因此答案是 \sum p_{i,L}(1-e_{i,L})siz_i。