本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-10 14:51:30

这个 DP 的样式非常奇诡。——LCA

LCA 模拟赛题，太困难了。基本是复述 LCA 给的题解。

题意

给出一个森林，点有点权 $a_u$，边有边权 $b_u$。标记一个点需要花费 $a_u$ 的代价，若其父亲已被标记，也可以花费 $b_u$ 的代价。标记随时可清除，且不能同时存在超过 $k$ 个标记点。要求树上的 $m$ 个点均被标记过，求最小代价。多组数据，$T\le 30,m\le n\le 5000,k\le 5$。原题。

弱化版：每个点只能被标记一次，$T\le 5,m\le n\le 10^5,k\le 10$。

题解

判掉 $k=1$，此时答案为 $\sum a$；将 $b_i$ 对 $a_i$ 取 $\min$，同时以 $0$ 为树根且不标记，避免讨论。考虑标记点形态，$k=2$ 时标记 $u$ 点后可向下拓展到子节点，但是需要清除 $u$ 点标记才能接着向下，最终能覆盖毛毛虫形状内的点。定义单点是 $1$ 合法的，对于 $i\gt 1$，定义 $u$ 子树 $i$ 合法当且仅当存在一个儿子 $i$ 合法， 且其他儿子均 $(i-1)$ 合法，这也能解释 $2$ 合法的形状。

于是对于弱化版，设 $f_{u,i}$ 表示 $u$ 子树内关键点均被标记过，且从 $u$ 开始的拓展过程 $i$ 合法的最小代价。状态不考虑 $u$ 点代价，因为其取值受父亲影响。另外令 $f_{u,0}$ 表示 $u$ 不选时的最小代价。转移为 $f_{u,1}=f_{u,0}=\sum\min(f_{v,k}+a_v,f_{v,0})$，对于 $i\gt 1$，有 $f_{u,i}=\min(f_{v,i}+b_v+\sum_{t\ne v}\min(f_{t,i-1}+b_t,f_{t,k}+a_t,f_{t,0}))$，只需先对第二个式子求和，再找最优差值更新即可。最后若 $u$ 必须被标记，将 $f_{u,0}$ 赋为正无穷，复杂度 $\mathcal O(nk)$。

对于原题，同一个点可被学习多次，即可以从 $u$ 拓展到 $v$，在 $v$ 拓展的过程中扔掉 $u$，之后需要标记 $v$ 或其他子节点时再把 $u$ 标记回来。据此设 $f_{u,i,j}$ 表示考虑 $u$ 子树，用到了至多 $i$ 的空间，过程中 $u$ 的子节点拓展需要 $u$ 点标记 $j$ 次的最小花费。与上面相同，状态不考虑 $u$ 点代价，这会在父亲节点上决策。

这个状态在定义什么？其包含子树内其他点的标记次数和方式，记录过程中的最大空间消耗和 $u$ 用于拓展的标记次数，以便向上转移。由于空间越大越可操作，$f_{u,i,j}$ 随 $i$ 增大单调不增。另外 $f_{u,i,0}$ 并非不标记 $u$，而是已经考虑的过程没有用 $u$ 拓展，还没有因此标记过 $u$。最终 $f_{u,i,0}$ 的值是无意义的，事实上代表的是 $i'\lt i$ 的 $f_{u,i',y}$，该状态也不能转移给父亲。至于真的不标记，再设 $g_u$ 表示 $u$ 不用于拓展时子树内最小代价，此时子树内其他拓展过程均可使用 $k$ 的空间，不用记录。

由于从某点开始同时向多个子树拓展不优，可以依次处理每个子树，这样可用空间更大。于是可依次将每个子树 $v$ 的信息拼到 $u$ 上。具体地，新拼上一个子树 $v$ 时，有以下几种转移（$t_v$ 表示 $v$ 是否需要标记；均有限制 $i\ge 2,j\ge 0,y\ge 1$）：

1. $v$ 从 $u$ 拓展来，且拓展过程中一直保留 $u$，$v$ 标记 $y$ 次：$f_{u,i,j}+f_{v,i-1,y}+yb_v\rightarrow f'_{u,i,j}$。
2. $v$ 从 $u$ 拓展来，且 $v$ 不用于向下拓展：$f_{u,i,j}+g_v+t_vb_v\rightarrow f'_{u,i,j}$。
3. $v$ 部分从 $u$ 拓展来，过程中扔掉 $u$，$v$ 标记 $y$ 次，其中 $x$ 次从 $u$ 拓展：$f_{u,i,j}+f_{v,i,y}+xb_v+(y-x)a_v\rightarrow f'_{u,i,j+x}$，有限制 $0\le x\le y$。
4. $v$ 不从 $u$ 拓展，标记 $y$ 次：$f_{u,i,j}+f_{v,k,y}+ya_v\rightarrow f'_{u,i,j}$；$v$ 不标记代价为 $g_v+t_va_v$，不如 2 优。
5. $u$ 不向下拓展，$v$ 标记 $y$ 次：$g_u+f_{v,k,y}+ya_v\rightarrow g'_u$；$v$ 不标记：$g_u+g_v+t_va_v\rightarrow g'_u$。

最难理解的可能是转移 3，即 $v$ 用了全部的 $i$ 空间，此时每次从 $u$ 拓展都要重新标记 $u$。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。

至于初始值，开始的时候只有单点 $u$，所有值均为 $0$。$f_{u,1}$ 没有转移，注意到此时 $u$ 同样不能向下拓展，全部赋成 $g_u$ 即可。暴力实现的话，转移 2.4.5 的复杂度不超过 $\mathcal O(n^2k)$，可以接受；而转移 1 是 $\mathcal O(n^3k)$ 的，转移 3 不限制上下界是 $\mathcal O(n^4k)$ 的，均需优化。

对于转移 1，注意到是对所有 $y$ 取最小值，于是设 $h_{i}=\min(f_{v,i,y}+yb_v)$，转移就变成了 $f_{u,i,j}+h_{i-1}\rightarrow f'_{u,i,j}$。这样转移和 $h$ 的预处理都是 $\mathcal O(n^2k)$ 的了，可以接受。

对于转移 3，注意到下标变化只与 $x$ 有关，先用同样方法避免掉 $y$ 的枚举。具体地，对于确定的 $i,j,x$，会用 $y\ge x$ 的 $f_{v,i,y}+xb_v+(y-x)a_v$ 转移。将 $y$ 分离出来得到 $f_{v,i,y}+ya_v$，预处理其后缀最大值 $h_{i,y}$ 即可，复杂度同样是 $\mathcal O(n^2k)$ 的。之后转移为 $f_{u,i,j}+h_{i,y}+x(b_v-a_v)\rightarrow f'_{u,i,j+x}$。注意到 $j$ 一维显然不会超过子树大小，可以套用树形背包，复杂度就是 $\mathcal O(n^2k)$ 的了。

于是做到了 $\mathcal O(n^2k)$ 的时空复杂度， 单组数据就能过了。然而原题是 $30$ 组多测，根本不是人。不过还有常数优化！考虑一次 $i$ 合法的拓展，若新覆盖的点数少于 $i$，则其一定也是 $(i-1)$ 合法的，可以将其拼到某次 $i$ 合法的拓展上。因此一次 $i$ 合法的拓展至少新覆盖 $i$ 个点，于是 $f_{u,i,j}$ 的 $j$ 一维可限制 $j\le \lceil\frac {s_u} i\rceil$。加上这个常数大大减小，可以通过。

代码

见云剪切板。