P15454 [JOI 2026 SemiFinal] 顺流而下 / River Rafting 笔记

考虑一个点会被谁照亮。易发现对于一条链，强度随着深度增加而减小，因此，一个点不会被其子树点亮。同理，若点 $u$ 被非祖先 $x$ 点亮，可以视作被 $\mathrm{LCA}(u,x)$ 点亮。

因此，一个点点亮的范围可以看作一个以自己为根的子树的范围。设 $f_{u,i,j}$ 表示子树 $u$ 内共被点亮了 $i$ 次（当前已经经过了 $u$ $i$ 次），计划之后总共通过点亮 $u$ $j$ 次来覆盖子树 $\le j$ 距离，的最小代价。

这样设计状态的原因是，可以随着递归将 $j$ 不断往上带，在上方做决策，实现“由祖先点亮”的目的。

先考虑合并来自儿子的答案

$$f_{u,i_1+i_2,j}^{\prime }\leftarrow min\{f_{u,i_1,x}+f_{v,i_2,y}\}$$

根据状态定义，只要 $x,y\le j$ 就是合法的，那么对于 $j$ 这一维是前缀 $min$，$O(1)$ 维护。$i\le {\mathrm{sz}}_u$，属于树形背包，$O(n^2)$。

由于到 $u$ 是又上了一层，因此需要的是再多点一次，不好一边合并一起做，可以最后一起做：$f_{u,i,j}^{\prime }\leftarrow f_{u,i,j-1}$

边界条件为 $f_{u,i,j}=+\mathrm{\infty }$，$f_{u,0,0}=0$。

最后决策是否要在这一层继续点亮 $j-i$ 次中的若干次，但从计数的角度考虑可以发现，如果在 $u$ 点亮一点再留一点给祖先点亮，是存在另一种 $j^{\prime }$ 的转移路径也是这样的，因此决策是否在 $u$ 点直接点亮全部 $j-i$ 次即可。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^3)$，把 DP 数组用 vector 存储即可做到 $O(n^2)$ 空间。