Creator's World

树形 dp 可以说是最重要的 dp 之一了。

一、特点

• 有明显的树形结构，所求的值可以分解成求每一棵子树的值（也就是形式相同，这也是 dp 的基本特点）

• 一般用儿子去更新父亲（也就是自下而上）

• 通常通过递归的形式求解

二、类型

1. 最小权覆盖集

基础的树形 dp 模型。每个点会覆盖相连的边（或相邻的点），求覆盖整棵树的最小权值。

这类型的题目要点在于状态时要根据每个点影响的范围设计，转移考虑每个节点每种情况有什么地方转移来。

P2016 战略游戏

设 $f_{u,0/1}$ 表示 $u$ 这个点放 $/$ 不放士兵的最少的士兵数目。因为每条边都要覆盖到，所以若 $u$ 不放士兵的话那么它的所有子节点都需要放士兵，有转移 $f_{u,0} = \sum f_{v,1}$；而若 $u$ 放士兵的话，它的子节点可放可不放，取 $\min$ 就好了，有转移 $f_{u,1} = 1 + \sum \min(f_{v,0}, f_{v,1})$。

P2899 [USACO08JAN]Cell Phone Network G

相比前面的会覆盖边来说，这种会覆盖点的会更加困难。因为上一种只需要考虑儿子的情况就可以了，但是这种就需要多考虑父亲影响的情况。因此我们要多用一种状态表示，设 $f_{u,0}$ 表示被儿子覆盖的最小点数，$f_{u,1}$ 表示被自己覆盖的最小点数，$f_{u,2}$ 表示被父亲覆盖的最小点数。$f_{u,1}$ 和 $f_{u,2}$ 都很好转移

$f_{u,1} = 1 + \sum \min(f_{v,0},f_{v,1},f_{v,2})$

$f_{u,2} = \sum \min(f_{v,0}, f_{v,1})$

重点是 $f_{u,0}$ 的转移，有一些难度。显然 $u$ 要被儿子覆盖，它的子节点一定要有一个被自己覆盖，剩下的就和 $f_{u,2}$ 一样，所以有转移

$f_{u,0} = \min(f_{u,0}, f_{u,2} - \min(f_{v,0}, f_{v,1}) + f_{v,1})$

P2458 [SDOI2006]保安站岗

上题的双倍经验。

P2279 [HNOI2003]消防局的设立

相比起来难了些。每个点都会影响向上的两个点和向下的两个点，因此我们设计状态要考虑到每种情况。设 $f_{u,0/1/2/3/4}$ 表示覆盖 $u + 2/1/0/-1/-2$，为了便于转移，我们需要加一些限制，这里的覆盖指的是以该点为根的子树中所有节点都要被覆盖，然后依次转移即可。

2. 树上背包

一般是处理树上有依赖性的问题。

P1272 重建道路

显然这里的剩下节点数就是价值，删边数是代价，可以转化为背包做。设 $f_{u,i}$ 表示以 $u$ 为根节点的子树只剩下 $i$ 个点的最小删边数，有转移 $f_{u,i} = \min(f_{u,i},f_{u,i - k} + f_{v,k} - 1)$，$-1$ 是因为 $u$ 和 $v$ 连的边不能删。

P3354 [IOI2005]Riv 河流

其他

P1131 [ZJOI2007] 时态同步

其实挺水的。因为树上到某个点的路径是唯一的，所以设 $f_u$ 表示 $u$ 到以 $u$ 为根的子树中的叶节点距离相同的最小操作，$g_u$ 表示 $u$ 到以 $u$ 为根的子树中的叶节点的距离，然后因为只能加不能减，就是要取最大的。