动态规划系统课程 · 第五讲：树形 DP¶
这一讲开始进入一个非常重要的 DP 分支：树形 DP。
前面我们学习了：
- 线性 DP：
dp[i] - 背包 DP：
dp[j] - 区间 DP：
dp[l][r]
今天学习：
dp[u][...]
其中 u 是树上的一个节点。
一、什么是树形 DP？¶
先看一棵树：
1
/ | \
2 3 4
/ \
5 6
如果题目要求我们：
在这棵树上选择一些节点，使得满足某种条件，并求最大值/最小值/方案数。
通常可以考虑：
树形 DP¶
树形 DP 的核心思想其实并不神秘：
把一个节点的子树看成一个独立的小问题，然后利用子树的答案计算当前节点的答案。
二、为什么树特别适合 DP？¶
因为树具有一个非常重要的性质：
从一个节点向下看，它的每棵子树之间互不影响。
例如：
1
/ | \
2 3 4
/ \
5 6
节点 1 的三个子树：
以 2 为根的子树
以 3 为根的子树
以 4 为根的子树
彼此之间没有边连接。
所以：
1
/ | \
子树2 子树3 子树4
我们可以分别计算：
dp[2]
dp[3]
dp[4]
然后再计算：
dp[1]
这就是树形 DP。
三、树形 DP 与 DFS 的关系¶
这是初学者最容易混淆的地方。
一定要区分：
DFS¶
是一种：
遍历树的方法。
DP¶
是一种：
保存并利用子问题答案的方法。
两者可以结合：
DFS
↓
先计算儿子
↓
得到儿子的 DP
↓
计算当前节点 DP
所以树形 DP 最常见的代码结构就是：
void dfs(int u, int fa) {
for (int v : tree[u]) {
if (v == fa)
continue;
dfs(v, u);
}
// 根据所有儿子的 dp
// 计算 u 的 dp
}
注意：
先 DFS 儿子，再计算父亲。
这实际上就是树上的一种“后序遍历”。
四、第一道经典题：树的最大独立集¶
我们从最经典的树形 DP 开始。
题目¶
给定一棵树。
要求选择尽可能多的节点，使得：
任意一条边的两个端点不能同时被选择。
例如：
1
/ \
2 3
/ \
4 5
如果选择：
1
那么：
2、3
不能选择。
如果不选择 1，那么：
2、3
就有机会选择。
五、什么叫独立集？¶
一个节点集合，如果满足：
任意两个被选择的节点之间没有直接的边。
那么这个集合叫：
独立集¶
目标是：
求最大独立集的大小。
六、最关键的问题：状态怎么设计？¶
对于节点 u，有两种情况：
情况 1：选择 u¶
dp[u][1]
情况 2：不选择 u¶
dp[u][0]
定义：
$$
dp[u][0]
$$
表示：
在
u的子树中，不选择 u 时能够选择的最大节点数。
定义：
$$
dp[u][1]
$$
表示：
在
u的子树中，选择 u 时能够选择的最大节点数。
这两个状态非常重要。
七、如果选择 u，会发生什么？¶
假设：
u
/ \
v w
如果选择 u：
选择 u
那么它的直接儿子：
v
w
都不能选择。
因此：
$$
dp[u][1]
=
1+\sum dp[v][0]
$$
注意：
孙子节点仍然可以选择。
例如：
u
/
v
/
x
选择 u：
u ✓
v ✗
x ✓
所以不能简单地把整棵子树都放弃。
八、如果不选择 u 呢？¶
如果不选择 u：
u ✗
那么儿子：
v
可以：
- 选择
- 不选择
因此：
$$
dp[u][0]
=
\sum
\max(dp[v][0],dp[v][1])
$$
九、得到完整转移¶
对于每一个儿子 v：
如果选择 u：
$$
dp[u][1]
=
1+\sum dp[v][0]
$$
如果不选择 u：
$$
dp[u][0]
=
\sum \max(dp[v][0],dp[v][1])
$$
这就是树形 DP 最经典的状态转移之一。
十、为什么必须先计算儿子？¶
因为：
dp[u][0]
需要：
dp[v][0]
dp[v][1]
所以必须：
先算 v
再算 u
DFS 正好可以完成这个过程。
十一、完整 C++ 代码¶
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> tree[MAXN];
int dp[MAXN][2];
void dfs(int u, int father) {
// 选择 u
dp[u][1] = 1;
// 不选择 u
dp[u][0] = 0;
for (int v : tree[u]) {
if (v == father)
continue;
// 先计算子树
dfs(v, u);
// 不选择 u
// v 可以选，也可以不选
dp[u][0] += max(
dp[v][0],
dp[v][1]
);
// 选择 u
// v 一定不能选
dp[u][1] += dp[v][0];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1, 0);
cout << max(
dp[1][0],
dp[1][1]
) << '\n';
return 0;
}
十二、手算一个例子¶
考虑：
1
/ \
2 3
/ \
4 5
从叶子开始。
节点 4¶
没有孩子。
选择：
$$
dp[4][1]=1
$$
不选择：
$$
dp[4][0]=0
$$
所以：
dp[4] = {0, 1}
节点 5 同理：
dp[5] = {0, 1}
节点 2¶
节点 2 的孩子：
4、5
如果不选择 2：
$$
dp[2][0]
=
\max(0,1)+\max(0,1)
=2
$$
如果选择 2：
$$
dp[2][1]
=
1+0+0
=1
$$
因此：
dp[2] = {2, 1}
节点 3¶
节点 3 是叶子：
dp[3] = {0,1}
节点 1¶
如果不选择 1：
$$
dp[1][0]
=
\max(2,1)+\max(0,1)
$$
所以：
$$
dp[1][0]=2+1=3
$$
如果选择 1：
$$
dp[1][1]
=
1+dp[2][0]+dp[3][0]
$$
得到：
$$
1+2+0=3
$$
最终：
$$
\boxed{3}
$$
十三、树形 DP 的第一个核心模型¶
刚才这个问题可以总结成：
dp[u][0] = 不选 u
dp[u][1] = 选择 u
这是树形 DP 中非常重要的一种：
“选 / 不选”模型¶
以后看到：
- 节点选取
- 相邻节点不能同时选
- 选某节点会影响相邻节点
- 最大独立集
- 没有上司的舞会
首先考虑：
dp[u][0]
dp[u][1]
十四、第二道经典题：没有上司的舞会¶
这道题和刚才的最大独立集本质完全相同，但是题意更加贴近实际。
题目¶
公司有 n 名员工。
公司关系是一棵树：
老板
|
├── 员工
│ ├── 下属
│ └── 下属
每个员工有一个快乐值：
happy[i]
如果某个员工参加舞会，那么他的直接上司不能参加。
要求：
求所有参加员工的快乐值总和最大是多少。
十五、状态定义¶
仍然是：
$$
dp[u][0]
$$
表示：
u不参加舞会时，u子树的最大快乐值。
$$
dp[u][1]
$$
表示：
u参加舞会时，u子树的最大快乐值。
十六、转移¶
如果 u 参加：
u ✓
那么所有直接下属不能参加：
$$
dp[u][1]
=
happy[u]
+
\sum dp[v][0]
$$
如果 u 不参加：
u ✗
那么每个下属可以自由选择：
$$
dp[u][0]
=
\sum
\max(dp[v][0],dp[v][1])
$$
是不是和上一道题一模一样？
是的。
十七、完整 C++ 实现¶
这里稍微增加一个重要知识点：
树的根不一定是 1。
所以我们需要找到真正的根节点。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> tree[MAXN];
long long happy[MAXN];
long long dp[MAXN][2];
void dfs(int u) {
// u 参加
dp[u][1] = happy[u];
// u 不参加
dp[u][0] = 0;
for (int v : tree[u]) {
dfs(v);
// u 不参加
dp[u][0] += max(
dp[v][0],
dp[v][1]
);
// u 参加
dp[u][1] += dp[v][0];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> happy[i];
}
vector<int> hasParent(n + 1, 0);
for (int i = 1; i < n; i++) {
int boss, employee;
cin >> boss >> employee;
tree[boss].push_back(employee);
hasParent[employee] = 1;
}
int root = 1;
for (int i = 1; i <= n; i++) {
if (!hasParent[i]) {
root = i;
break;
}
}
dfs(root);
cout << max(
dp[root][0],
dp[root][1]
) << '\n';
return 0;
}
十八、这道题告诉我们一个非常重要的事情¶
树形 DP 不一定是在：
无根树
上直接做。
很多题目实际上给的是：
父亲 → 儿子
这样的有向关系。
这时候可以直接从根开始 DFS。
十九、第三道题：树的最大路径和¶
现在我们学习一个不同类型的树形 DP。
给定一棵带权树：
1
/ \
2 3
/ \
4 5
每个节点有一个权值。
求：
树中任意两个节点之间路径上的最大权值和。
这道题非常经典，因为它告诉我们：
树形 DP 不一定只有“选 / 不选”。
二十、先思考：路径是什么？¶
假设路径经过节点 u：
x
|
v
|
u
|
w
|
y
一条经过 u 的路径最多可以：
从一个方向进入
u，再从另一个方向离开u。
所以在 u 这里，最多连接两条向下的路径。
这就给了我们状态设计的灵感。
二十一、定义状态¶
定义：
$$
dp[u]
$$
表示：
从节点
u出发，向它的子树方向走，能够得到的最大路径和。
也就是：
从 u 开始
只能向下面走
二十二、如何计算 dp[u]？¶
假设 v 是 u 的一个儿子。
如果我们从 u 走向 v：
u → v → ...
可以得到：
$$
dp[v]
$$
因此：
$$
dp[u]
=
w[u]
+
\max(0,\max dp[v])
$$
为什么是：
max(0, ...)
因为如果所有子树贡献都是负数：
还不如不走。
二十三、但是最终答案不一定只有一条向下路径¶
例如：
u
/ \
v w
最大路径可能是：
v
\
u
\
w
也就是：
最长向下路径1
+
u
+
最长向下路径2
因此我们需要维护：
u的两个最大的正向子树贡献。
假设最大的两个贡献是：
best1
best2
那么经过 u 的最大路径：
$$
best1+w[u]+best2
$$
二十四、完整 C++ 实现¶
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> tree[MAXN];
long long w[MAXN];
long long dp[MAXN];
long long answer;
void dfs(int u, int father) {
// 最大的两个子树贡献
long long best1 = 0;
long long best2 = 0;
for (int v : tree[u]) {
if (v == father)
continue;
dfs(v, u);
long long value = dp[v];
if (value > best1) {
best2 = best1;
best1 = value;
} else if (value > best2) {
best2 = value;
}
}
// 从 u 向下走的一条最大路径
dp[u] = w[u] + best1;
// 一条经过 u 的完整路径
answer = max(
answer,
w[u] + best1 + best2
);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
answer = LLONG_MIN;
dfs(1, 0);
cout << answer << '\n';
return 0;
}
二十五、这道题和前两道有什么不同？¶
前两道：
dp[u][0]
dp[u][1]
是两个状态。
第三道：
dp[u]
只有一个主要状态。
但我们在转移时维护：
best1
best2
因此可以看到：
树形 DP 没有固定的状态形式。
并不是看到树就一定：
dp[u][2]
真正应该做的是：
根据题目的结构设计状态。
二十六、树形 DP 的标准模板¶
对于普通的无根树：
void dfs(int u, int father) {
// 初始化 dp[u]
for (int v : tree[u]) {
if (v == father)
continue;
dfs(v, u);
// 利用 dp[v]
// 更新 dp[u]
}
}
这个模板一定要掌握。
二十七、为什么需要 father？¶
因为普通树的邻接表是双向存储的：
tree[u].push_back(v);
tree[v].push_back(u);
例如：
1 —— 2
那么：
tree[1] = {2}
tree[2] = {1}
如果：
dfs(1, 0);
进入 2：
dfs(2, 1);
此时 2 又看到：
1
如果没有判断：
if (v == father)
continue;
就会：
1 → 2 → 1 → 2 → 1 ...
无限递归。
所以：
dfs(u, father)
中的 father 非常重要。
二十八、树形 DP 的本质¶
现在我们可以把树形 DP 总结成一句话：
先通过 DFS 解决所有子树，再利用子树答案计算当前节点答案。
也就是：
当前节点 u
↑
┌─────────┼─────────┐
↑ ↑ ↑
dp[v1] dp[v2] dp[v3]
↑ ↑ ↑
子树 子树 子树
这实际上就是：
后序遍历 + 动态规划¶
二十九、树形 DP 最容易犯的 6 个错误¶
错误 1：没有定义状态含义¶
错误：
dp[u][0]
dp[u][1]
直接开始写。
正确做法：
先用中文明确说明
dp[u][0]和dp[u][1]分别表示什么。
错误 2：没有先 DFS 儿子¶
错误：
先算 u
再算 v
正确：
v
↓
dp[v]
↓
u
↓
dp[u]
错误 3：无根树没有排除父节点¶
必须：
if (v == father)
continue;
错误 4：把 DFS 和 DP 混为一谈¶
DFS：
决定访问顺序。
DP：
保存子问题答案。
两者不是同一个概念。
错误 5：认为树形 DP 只能求最大值¶
实际上可以求：
- 最大值
- 最小值
- 方案数
- 是否可行
- 最大路径
- 最小费用
- 某种计数
错误 6：递归深度过大¶
如果：
1 - 2 - 3 - 4 - ... - 100000
是一条链。
递归 DFS 可能出现栈深度问题。
竞赛中如果 n 非常大，需要考虑：
- 非递归 DFS
- 调整栈空间
- 根据题目环境决定实现方式
初学阶段先掌握递归版本。
三十、四种 DP 放在一起比较¶
现在我们已经学习：
| DP 类型 | 核心状态 | 核心问题 |
|---|---|---|
| 线性 DP | dp[i] |
前面的状态如何转移 |
| 背包 DP | dp[j] |
物品如何选择 |
| 区间 DP | dp[l][r] |
大区间如何拆 |
| 树形 DP | dp[u][...] |
子树如何合并 |
可以把它们理解为：
线性 DP
↓
沿着序列解决问题
背包 DP
↓
沿着物品 + 容量解决问题
区间 DP
↓
沿着区间长度解决问题
树形 DP
↓
沿着树的后序结构解决问题
三十一、一个非常重要的提升：树形 DP其实是“有向无环结构上的 DP”¶
把树从根节点开始看：
1
/ | \
2 3 4
/ \
5 6
如果规定所有边都从父亲指向孩子：
1 → 2
1 → 3
1 → 4
2 → 5
2 → 6
那么实际上形成了一个：
有向无环图
所以树形 DP 和后面要学习的：
DAG DP¶
存在非常密切的联系。
三十二、动态规划知识地图更新¶
目前已经完成：
动态规划
│
├── ① 线性 DP
│ ├── LIS
│ ├── LCS
│ └── 编辑距离
│
├── ② 背包 DP
│ ├── 01 背包
│ ├── 完全背包
│ ├── 多重背包
│ └── 分组背包
│
├── ③ 区间 DP
│ ├── 石子合并
│ ├── 回文
│ └── 矩阵链
│
└── ④ 树形 DP
├── 最大独立集
├── 没有上司的舞会
└── 树的最大路径和
三十三、本讲最重要的三个模板¶
模板 1：树上“选 / 不选”¶
dp[u][1] = 选择 u 的最优值;
dp[u][0] = 不选择 u 的最优值;
for (int v : tree[u]) {
if (v == father)
continue;
dfs(v, u);
dp[u][1] += dp[v][0];
dp[u][0] += max(
dp[v][0],
dp[v][1]
);
}
模板 2：树上的子树贡献¶
dp[u] = 初始值;
for (int v : tree[u]) {
if (v == father)
continue;
dfs(v, u);
dp[u] = 根据 dp[v]
更新 dp[u];
}
模板 3：树上的“两个最大贡献”¶
long long best1 = 0;
long long best2 = 0;
for (int v : tree[u]) {
if (v == father)
continue;
dfs(v, u);
if (dp[v] > best1) {
best2 = best1;
best1 = dp[v];
}
else if (dp[v] > best2) {
best2 = dp[v];
}
}
这个技巧在：
树的直径、最大路径、树上路径问题
中非常常见。
三十四、课后训练¶
建议按下面顺序练习：
Level 1¶
- 树的最大独立集
- 没有上司的舞会
- 树的最大路径和
Level 2¶
- 树的最小点覆盖
- 树的最小支配集
- 树上最大权独立集
Level 3¶
- 树上背包
- 有依赖的背包
- 树上路径统计
- 换根 DP
其中 换根 DP 非常重要，它会成为后面学习高级树形 DP 的关键。
下一讲：DAG DP¶
下一阶段我们将学习一个非常自然的内容：
第六讲：DAG 上的动态规划¶
重点解决：
什么是 DAG？
为什么拓扑排序可以做 DP？
DFS DP 和拓扑 DP 有什么区别？
然后通过三道经典问题学习：
- 有向无环图最长路
- DAG 上的路径计数
- 关键路径 / 最长路径
并进一步理解一个非常重要的统一观点：
动态规划的本质，不是某一种固定代码，而是在一个“状态图”上按照依赖关系计算答案。
这句话理解之后，线性 DP、区间 DP、树形 DP、DAG DP 会开始真正串成一个整体。