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

· · 题解

我常常找寻过去。recollect 和 recall 等价。退背包是啥？我不会。

由期望的线性性，我们只需要求出每个点 u 是轻儿子的概率 P_u，最后将 \mathit{siz}_u \times P_u 全部相加即可得到答案。

考虑从下到上处理，设 f_{u, i} 表示当前处理完 u 子树，包含 u 的重链长度为 i 的概率。

如果给定树是一棵二叉树，有一个比较容易的做法。设 l, r 表示 u 的两个子节点，那么可以枚举两个子节点的重链长度 x, y，有：

f_{u, x + 1} \overset + \gets f_{l, x} f_{r, y} \times \frac{x}{x + y}\\ P_l \overset + \gets f_{l, x} f_{r, y} \times \frac{y}{x + y}\\

反过来类似。因为第二维的大小是最大子树深度 \mathit{md}_u，所以直接做复杂度为 O(n^2)。证明和长链剖分优化 dp 是一样的。

当有多个子树的时候，考虑从前往后依次合并两个子树。例如三个子树的长度为 a, b, c，那么先合并 a, b，其中 a 胜出的概率为 \frac{a}{a + b}。之后，我们要将 (a, b) 和 c 进行合并。由题目信息，a 最终胜出的概率是 \frac{a}{a + b + c}，是“a 胜出 b”的概率的 \frac{a + b}{a + b + c} 倍。这相当于一个大小为 (a + b) 的子树和 c 进行合并。

设 u 有若干个儿子 v_1, \dots, v_k，对应的链长为 s_1, \dots, s_k。那么 v_i 能够胜出的条件有三个：

第一个其实不太能说是条件，我们可以将其中 \le i 的 j 取到 s_j 的并到第二个条件，将 \gt i 的并到第三个条件。对于第二个，我们可以设 g_{i, j} 表示前 i 个儿子的长度和为 j 的概率，这个可以直接背包求出：枚举前 i 个儿子的和 S，

g_{i, S} \overset + \gets g_{i - 1, S - s_i} \times f_{v_i, s_i}

第二个条件成立的概率就是：

g_{i, S} \times \frac{s_i}{S}\\

第三个条件可以倒过来做。设 h_{i, S} 表示前 i 个儿子和为 S（这是条件，不需要乘上和为 S 的概率）在后续能够胜出的概率。初始是 h_{k, S} = 1（因为重儿子肯定存在）。然后有转移：

h_{i - 1, S - s_i} \gets h_{i, S} \times f_{i, s_i} \times \frac{S - s_i}{S}\\

第三个条件成立的概率就是 h_{i, S}。

直接模拟，就是 O(n^2) 的了。

pdl：这个题比绿难，所以我不能发工单了。