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

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

因此，一个点点亮的范围可以看作一个以自己为根的子树的范围。设 $f_{u,i,j}$ 表示子树 $u$ 内共被点亮了 $i$ 次（当前已经经过了 $u$ $i$ 次），想要再点亮 $u$ $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$。

最后决策是否要在这一层继续点亮 $u$ $j$ 次，即 $f_{u,i+1,j-1}^{\prime }\leftarrow min(f_{u,i+1,j-1},f_{u,i,j})$。

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