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

· · 题解

考虑先处理 $l=\sum l_i$ 的概率，直接树上背包即可。 枚举 $u$ 的重儿子 $v$，需要将除了 $v$ 的背包与 $v$ 拼接。若前缀拼后缀是 $O(n^3)$ 的。 发现合并子树背包本质为多项式乘法，考虑总背包多项式除以 $v$ 背包。以上**暴力计算，不需要多项式算法**。 算答案不难，令 $s_u$ 为 $u$ 子树大小，若 $p$ 的概率选了子树 $v$ 对答案贡献 $p(s_u-s_v-1)$。 没判除数首项 $≡0$ 警钟长鸣。 :::info[多项式？] $f_{u}$ 可以写作多项式 $\displaystyle \sum\limits_lf_{u,l}x^l$，背包合并等价于多项式乘法。 或者可以看成不进位的高精度；暴力多项式除法按照因式大除法模拟即可。 ::: :::info[时间复杂度] 对于暴力多项式除法，考虑树上背包时间复杂度的证法，$\displaystyle \sum\limits_u\sum\limits_{fa_v=u}s_v(s_u-s_v)=O(n^2)$（每两个点只在 lca 贡献） 当然逆元复杂度有个 $O(n\log_2n$)。 ::: :::info[前后缀拼接] 整体挖掉一个的 trick。 如多次查询 $a_1,a_2,...,a_{i-1},a_{i+1},...,a_n$ 的极值，取 $i-1$ 结尾的前缀极值和 $i+1$ 开头的后缀极值的极值。 常见于树形 dp（刨去当前子树）。 :::