第四十九章 动态规划——树形DP模型

• 一、树形DP
• 二、例题
• • 1、背包模型 + 树形DP
  • • （1）AcWing 10. 有依赖的背包问题
    • （2）AcWing 1074. 二叉苹果树
  • 2、状态机DP + 树形DP
  • • （1）AcWing 285. 没有上司的舞会
    • （2）AcWing 323. 战略游戏
    • （3）AcWing 1077. 皇宫看守
  • 3、其他
  • • （1）AcWing 1072. 树的最长路径
    • （2）AcWing 1073. 树的中心

一、树形DP

树形DP其实和普通的DP没有什么区别，我们之前的数据之间都是线性关系的，比如普通的背包问题，那些物品被摆成了一条线，即存储在一个数组中。

因此对于这种存在数组中的数据，我们在循环设计的时候，只需要写一个forforfor循环即可。但是我们今天所介绍的问题中，这些用到的数据被存储在了树上。

所以当我们解决子问题的时候，往往需要用DFS去遍历树。而这个DFS的作用其实就是之前所说的for循环的作用。（往往只用DFS代替原先的最外层for循环)。

这种题目其实就认为是树形DP。

那么我们发现，对于树形DP而言，其实只是将数据的存储换了个方式，而状态方程的书写往往还需要用到之前的模型，因此我们树形DP的例题往往是结合了其他模型的。

二、例题

1、背包模型 + 树形DP

（1）AcWing 10. 有依赖的背包问题

这道题是树形DP和分组背包的一个结合，其变化在于，我们将根节点的一棵子树看作一个物品组。
详解请看：AcWing 10. 有依赖的背包问题（分组背包问题 + 树形DP）

（2）AcWing 1074. 二叉苹果树

这道题其实也是树形DP和分组背包的结合，依旧是将根节点的子树看作一个物品组。

AcWing1074. 二叉苹果树（树形DP +分组背包）

2、状态机DP + 树形DP

下面三道题都涉及到了状态机DP，因为题目中当前节点的状态影响到了后续子树的选择，甚至当前节点父节点的状态都影响到了当前节点子树的选择问题，因此这三道题我们需要将某个节点状态分类讨论。

（1）AcWing 285. 没有上司的舞会

AcWing285.没有上司的舞会（树形DP + 状态机DP）

（2）AcWing 323. 战略游戏

AcWing 323. 战略游戏（树形DP + 状态机DP）

（3）AcWing 1077. 皇宫看守

AcWing 1077. 皇宫看守（树形DP + 状态机DP）

3、其他

后面的题没有明显的模型，只是用到了树形dp，而第二道题树的中心里还用到了换根DP，我们的普通的树形dp是用子节点更新父节点，换根dp是用根节点去更新子节点。

（1）AcWing 1072. 树的最长路径

AcWing 1072. 树的最长路径（DFS与树形DP）

（2）AcWing 1073. 树的中心

AcWing 1073. 树的中心（详解树形DP和换根DP）