给出一个森林，点有点权 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）：
最难理解的可能是转移 3，即 v 用了全部的 i 空间，此时每次从 u 拓展都要重新标记 u。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。