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

· · 题解

对于 \sum l_i 其处理较为困难，因此我们需要记录 f_{u,k} 作为 u 子树里面记忆段长度为 k 的概率。对于其转移，我们需要知道长度和，考虑背包。对于 u 子树，考虑 g_{i,j} 为现在选择的记忆段长度为 i，记忆段总长度为 j。考虑转移，我们需要钦定某个子树 v 作为连接 u 的记忆链路。那么 g_{i,j} \leftarrow g_{i,j}+g_{0,j-i}\times f_{v,i}。对于不与 u 连接的子树 v，g_{i,j}\leftarrow g_{i,j}+g_{i,j-k}\times f_{v,k}，当子树转移完后，f_{u,k}=\sum_{j=k}^n \dfrac{g_{j,k}}{j}，即为 f_{u,k} 的值，这部分复杂度 O(n^3)。

现在考虑计算答案，对于上面这个式子，可以类似的计算答案。因为除了连接记忆链路的子树 v，其它 w 子树在 u 这一层的贡献为 siz_w。也就是 v 子树实际贡献为 siz_u-1-siz_v。考虑 h_{i,0/1} 为记忆段总长度为 i ，是否选择过记忆段进行连接。如果选择连接，那么转移为 h_{i,1}\leftarrow h_{i,1}+h_{i-j,0}\times f_{v,j}\times (siz_u-1-siz_v)。如果不连接，则转移为 h_{i,0}\leftarrow h_{i,0}+h_{i-j,0}\times f_{v,j}。转移完后，最终答案加上 \sum_i \dfrac{h_{i,1}}{i}，这部分复杂度 O(n^2)。最终我们得到一个初版的 O(n^3) 算法。

考虑对第一部分进行优化。如果我们忽视选择的记忆段，只考虑长度和，那么是一个平凡 O(n^2) dp。而对于 g，如果我们选择一个 v 作为连接记忆段的子树，那么实际上对 g 的贡献为除了 v 之外其它子树的 dp 值 g'_0 乘上自己的 f，也就是 g_{i,j}\leftarrow g_{i,j}+g'_{0,j-i}\times f_{v,i}。如何得到 g'_0？我们考虑对于 g_0，实际上是一个平凡的背包，因此是无序的，那么我们可以在里面撤回 v 的贡献。也就是 g'_{0,i}=g_{0,i}-\sum_{j=1}^{\min\{i-1,maxd_j\}}g'_{0,i-j}\times f_{v,j}。通过这样改进后，u 的各个儿子 v_1,v_2,\dots,v_k 的 maxd 之和为 slen，则 u 处操作次数为 \sum_k (slen-maxd_{v_k})maxd_{v_k}，看上去似乎是 O(n^3)，但实际上考虑树形背包复杂度证明类似的分析，(slen-len_{v_k})len_{v_k} 相当于 v_k 内最长链和 u 其它儿子最长链两两配对，同时由于都是最长链在配对，所以两两之间最多配对一次，时间复杂度为 O(n^2)。

另一个更直观的想法是对于 maxd_i，我们考虑能否进行长剖使其变成 O(n)，那么我们就需要对长儿子不进行撤回操作。我们发现这实际上是可行的。因为如果我们把长儿子放在最后加入 dp，那么在它之前已经得到了 g'，就可以直接 dp。而如果不进行撤回，按照普通的树形背包复杂度分析，其复杂度为 O(n^2)，因此每个部分的复杂度都优化到 O(n^2)，可以通过此题。