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

· · 题解

题解

考虑树上 DP，f(u,i) 表考虑 u 子树内，u 所在重链长 i 的概率，g(u,i) 表 u 的哥哥森林，这些根所在重链和为 i 的概率

设 \text{bro}_u 表 u 的哥哥，\text{son}_u 表 u 的最大儿子

g(u,i)=\sum_{j=0}^i f(u,j)g(\text{bro}_u,i-j)

考虑 f ，设 F(v,i) 表 \text{son}(\text{fa}_v) 的哥哥森林中，去掉 v 为根的树，所有根所在重链和为 i 的概率

F(v,i)=g(\text{son}(\text{fa}_v),i)-\sum_{j=0}^if(v,j)F(v,i-j)

因此有

f(u,i)=\sum_{(u,v)\in E} \sum_x \frac{i-1}{x}f(v,i-1) F(v,x)

对于 g ，因为 i\le \text{sz}_u ，显然复杂度为 O(n^2)

对于 f,F ，其复杂度为

\begin{align} T&\in O\left(\sum_{(u,v)\in E} (\text{sz}_u-\text{sz}_v)\text{sz}_v\right)+O(n^2)\\ &=O\left(\sum_{(u,v)\in E} \text{sz}_u\text{sz}_v-\text{sz}_v^2\right)+O(n^2)\\ &=O\left( \sum_u \text{sz}_u\sum_{(u,v)\in E} \text{sz}_v- \sum_u \text{sz}_u^2 \right)+O(n^2)\\ &=O\left( \sum_u \text{sz}_u^2- \sum_u \text{sz}_u^2 \right)+O(n^2)\\ &=O(n^2) \end{align}

最后容易统计答案

\text{ans}=\sum_{(u,v)\in E}\text{sz}_v\sum_i \sum_x \frac{i}{x}F(v,x)f(v,i)

杂话

笔者考场上乱搞证明了合并前后背包的复杂度是 “对的”，尽管会撤销背包（F(i,j)）但是因为已经写完合并背包且过了超级水的大样例所以没写，在考场 最后 10 分钟 造了个类菊花图把自己卡掉了，没时间改了

警示后人：做完一道题就造几个数据！

不过听同学说他们的假算都被大样例卡掉了，你看大样例这么强一定是大样例同款数据吧（