树型动态规划，顾名思义，在“树”上进行状态转移，状态转移关系往往建立在父节点和子节点之间，“树”上父子关系天然就是一个递归（重叠子问题），建立起父亲、儿子之间关系，然后记忆化搜索实现。 建立递推关系（状态转移方程），可以从这样两个方向进行：

（1）子节点→父节点，父节点的值建立在子节点基础上进行；

（2）父节点→子节点，已经得到整个树的信息，也就是父节点的值，求某一个字节的值，往往用于换根 Dp。

例1.P1352没有上司的舞会

【思路点拨】

对于一个节点，这个节点可以参加或不参加 $(0/1)$ 舞会。如果某个节点参加了，那么这个节点的子节点（下属）都不能来参加，如果这个节点没有参加，那么这个节点的子节点可以参加或者不能参加，那么定义 $f[x][1]$ 表示以 $x$ 节点为根的子树，节点 $x$ 参加的情况下，这颗子树的所能获得的最大快乐指数，$f[x][0]$ 节点 $i$ 不参加所能获得的最大快乐指数。

$r[x]$ 是节点 $i$ 的快乐指数。状态转移方程为：

$f[x][0]=\sum max(f[son_x][1],f[son_x][0])$

$f[x][1]=r[x]+\sum f[son_x][0]$

$ans=max(f[root][0],f[root][1])$

参考代码：

版本1：动态数组存树

版本2：链式前向星

例2.P2016 战略游戏

【思路点拨】

根据题意构建一张关系图，关系图是一颗树，点上安排士兵，用士兵看边，使用最少的士兵看住所有的边。（最少的点看住所有的边）

1.设 $f[x][1]$ 表示以 $x$ 为根的子树中，$x$ 安排士兵，以 $x$ 为根的子树需要最少士兵。此时 $x$ 的子节点可以安排士兵，也可以不安排。

$f[x][1]=1+\sum min(f[y][0],f[y][1])$,$y$ 是 $x$ 的子节点

2.设 $f[x][0]$ 表示以 $x$ 为根的子树中，$x$ 不安排士兵，以 $x$ 为根的子树需要最少士兵。此时 $x$ 的子节点 $y$ 必须安排士兵，否则边 $(x,y)$ 将无人瞭望。

$f[x][0]=\sum f[y][1]$,$y$ 是 $x$ 的子节点

$ans=min(f[root][0],f[root][1])$

参考代码：

版本1：动态数组

版本2：链式前向星

例3.P2458 [SDOI2006]保安站岗

题意简化，给定一棵，给树上一些点安排士兵看守树上所有的点，任意一个点都能看守其父亲、儿子，每个点安排士兵的费用不同，问要看守住所有树上的节点，最少花费是多少？（点看守点）

对于树上每一个点，这个点要被看守住，可能是被父亲看住、自己看自己、儿子看住$3$种情况，那针对这三种情况，设计状态转移如下：

1.$f[x][0]$：$x$ 被父亲看到，这时 $x$ 没有安排警卫，$x$ 的儿子要么安排警卫，要么被它的后代看到，则：

$f[x][0]=\sum min(f[y][1],f[y][2])$

2.$f[x][1]$：$x$ 被儿子看到，即 $x$ 的某个儿子安排了警卫，其他儿子需要安排警卫或者被它的后代看到，则：

$f[x][1]=(\sum min(f[y][1],f[y][2]) ) +d$

其中 $d= min(d,f[y][2]-min(f[y][1],f[y][2]))$

关于$d$的理解：$x$被儿子看到，那么$x$的所有儿子中至少有一个应该安排警卫，就会有两张情况：

（1）如果所有儿子 $f[y][1]<f[y][2]$,那么就需要找一个最小安排花费的儿子安排上警卫，即 $d$；

（2）如果至少有一个儿子 $f[y][1]<f[y][2]$ ,即众多儿子中至少有个已经安排了警卫，$d$ 此时为 $0$；

3.$f[x][2]$：$x$ 安排了警卫，$x$ 的儿子$y$ 可以安排警卫，也可以被 $y$ 的儿子看守，还可以被父亲看守，则：

$f[x][2]=h[x]+ \sum min(f[y][0],f[y][1],f[y][2])$

$ans=min(f[root][1],f[root][2])$,$root$ 没有父亲

时间复杂度 $O(n)$

参考代码：点击

---

学习完毕

{{ select(1) }}

• YES
• NO