【题解】[NOI2002] 贪吃的九头龙 树形 DP—chiimo

我水平很菜，你忍一下。

题面

树形 DP。

首先可以发现， $m>2$ 时，难受度只出现在最大的头吃的果子上（因为我把果子分成最大的头吃的和其他的，其他的里面，相邻的果子让不同的头吃即可）。

然后我定义 $f_{i,j,k}$ 为当前为 $i$ 节点，当前节点分 $j$ 个果子给最大的头，当前节点选择情况为 $k$（$1$ 选 $0$ 不选）。

那么对于每一个子节点，我们有
$$f_{u,j,0}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,0}+f_{u,j-t,0}+[m=2]w_i,f_{v,t,1}+f_{u,j-t,0} \} \},\\ f_{u,j,1}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,1}+f_{u,j-t,1}+w_i,f_{v,t,0}+f_{u,j-t,1} \} \}$$

解释：
当我当前节点不给最大头，那么 $f_{u,j-t}$ 的第三项只能取 $0$ ，同理，如果我当前节点不给最大头吃，那么 $f_{u,j-t}$ 的第三项只能取 $1$ 。

如果 $m=2$ ，那么当我当前节点和当前节点的子节点全部取 $0$ 时，就是说这两个点都给第二个头吃，那么答案要加上 $w_i$ ，否则不用（前面说过了）。

然后如果我当前节点和子节点全部给大头，那么这中间这段树枝必须加到答案里。

但是，这样做会导致更新过的 $f$ 再去更新别的 $f$ ，所以我们要把用来更新的 $f$ 拍到另一个数组 $g$ 中，则：
$$f_{u,j,0}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,0}+g_{j-t,0}+[m=2]w_i,f_{v,t,1}+g_{j-t,0} \} \},\\ f_{u,j,1}=\operatorname{min}\{ \operatorname{min}\{ f_{v,t,1}+g_{j-t,1}+w_i,f_{v,t,0}+g_{j-t,1} \} \}$$

这样方程就写完了。

另外，如果果子个数不够，那么答案就是 $-1$ 。

最终输出的答案就是 $f_{1,k,1}$ ，因为规定第一个点必须选。

代码