C++ 树形 DP解析

目录

• 树形DP：从原理到实战的深度解析（对话版）
• • 引言
  • 一、初识树形DP：它解决什么问题？
  • • 树形DP的典型特征：
    • 树形DP的前置知识
  • 二、树形DP核心框架：四步走
  • • 步骤1：树的存储（邻接表）
    • 步骤2：状态定义
    • 步骤3：递归遍历（DFS）
    • 步骤4：状态合并（核心）
    • 树形DP通用模板（伪代码）
  • 三、入门例题1：树的最大独立集
  • • 解题思路
    • 完整代码实现（C++）
    • 代码核心解析
  • 四、入门例题2：树的直径（最长路径）
  • • 问题定义
    • 解题思路
    • 完整代码实现（C++）
    • 核心区别与解析
  • 五、进阶例题1：树上背包（分组背包的树形版）
  • • 问题定义
    • 解题思路
    • 完整代码实现（C++）
    • 核心难点解析
  • 六、进阶例题2：树形DP的换根法（二次扫描）
  • • 问题定义
    • 解题思路
    • • 第一步：第一次DFS（自底向上）
      • 第二步：第二次DFS（自顶向下，换根）
    • 完整代码实现（C++）
    • 核心解析
  • 七、树形DP的常见坑点与优化
  • • 通用优化技巧
  • 八、树形DP的经典应用场景
  • 九、总结
  • • 核心要点回顾
    • 学习建议

树形DP：从原理到实战的深度解析（对话版）

引言

树形DP（树形动态规划）是动态规划中专门处理树形结构问题的分支，其核心是“以树的递归结构为依托，将子树的状态信息向上合并，最终得到整棵树的最优解”。树的天然递归特性（每个子树都是独立的树）与DP的“子问题最优解推导父问题最优解”思想高度契合，使得树形DP成为算法竞赛、面试中高频出现的考点。本文以“新手提问+导师解答”的对话形式，从树的基础遍历到树形DP的核心框架，再到经典例题的深度拆解，用超万字篇幅帮你彻底吃透树形DP。

一、初识树形DP：它解决什么问题？

新手：导师您好！我学完了线性DP、区间DP，现在接触树形DP完全摸不着头脑——树形DP的“树”体现在哪里？它和普通DP的核心区别是什么？ 导师：别急，咱们先从树形DP的核心特征入手： 树形DP的“树”，指的是问题的数据结构是树形结构（比如家族关系树、公司组织树、图的生成树等），且问题的最优解需要依赖子树的最优解来推导。

树形DP的典型特征：

举个最直观的例子：“树的最大独立集问题”——给定一棵有n个节点的树，选择若干节点，使得任意两个选中的节点不相邻，求最多能选多少个节点。这个问题中，节点u的选择状态（选/不选）直接影响子节点v的选择，且必须先知道所有子节点的最优解，才能计算u的最优解，完全符合树形DP的特征。

和普通DP的核心区别：

• 普通DP（如01背包、区间DP）的状态是线性/区间的，枚举顺序是“从左到右”“从小到大”；
• 树形DP的状态是基于节点的，枚举顺序是“自底向上”（先子树后父节点），依赖树的遍历（深度优先遍历DFS）实现。

树形DP的前置知识

在学习树形DP前，你需要掌握：

二、树形DP核心框架：四步走

新手：树形DP有没有通用的实现框架？我看不同例题的代码好像都有相似的递归结构。 导师：当然有！树形DP的实现框架高度固定，核心是“建图→状态定义→递归遍历→状态合并”，具体分四步：

步骤1：树的存储（邻接表）

树通常以无向图的形式给出（比如输入u和v表示边），需要用邻接表存储，并在遍历时标记父节点，避免重复访问（比如从父节点u到子节点v后，不再从v回到u）。

C++邻接表存储模板：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN]; // 邻接表
bool vis[MAXN]; // 标记是否访问过（或用父节点标记）

// 添加边
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}

步骤2：状态定义

树形DP的状态通常定义为dp[u][k]，其中：

• u：当前处理的节点；
• k：节点u的状态（比如“选/不选u”“u的子树中选m个节点”等，k的维度根据问题定）。

状态定义是树形DP的核心难点——必须结合问题要求，让状态能覆盖“子树的所有必要信息”，且能通过子节点的状态推导父节点的状态。

步骤3：递归遍历（DFS）

以根节点为起点（通常选1号节点，或根据问题指定），递归遍历每个节点的所有子节点：

步骤4：状态合并（核心）

根据问题的状态转移逻辑，将子节点v的dp[v][…]合并到父节点u的dp[u][…]中。比如：

• 若u选，则v不能选：dp[u][1] += dp[v][0]；
• 若u不选，则v可选可不选：dp[u][0] += max(dp[v][0], dp[v][1])。

树形DP通用模板（伪代码）

// 递归处理节点u，fa是u的父节点
void dfs(int u, int fa) {
// 初始化当前节点的状态（比如dp[u][0] = 0, dp[u][1] = w[u]）
init_dp(u);

// 遍历所有邻接节点
for (auto v : adj[u]) {
if (v == fa) continue; // 跳过父节点
dfs(v, u); // 递归处理子节点v

// 状态合并：将v的状态合并到u中
merge_dp(u, v);
}
}

int main() {
int n;
cin >> n;
// 输入n-1条边，构建邻接表
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
addEdge(u, v);
}

dfs(1, –1); // 以1为根，父节点为-1（无）
// 根据问题输出结果（比如max(dp[1][0], dp[1][1])）
cout << get_ans() << endl;
return 0;
}

三、入门例题1：树的最大独立集

新手：先从最简单的树形DP例题入手吧！树的最大独立集问题具体该怎么实现？ 导师：咱们先明确问题：

• 给定一棵n个节点的树，每个节点有一个权值（也可默认权值为1）；
• 选择若干节点组成独立集，要求任意两个选中的节点不相邻（无直接边相连）；
• 求独立集的最大权值和（若权值为1，则是最大节点数）。

解题思路

完整代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN]; // 邻接表
int w[MAXN]; // 节点权值
long long dp[MAXN][2]; // dp[u][0]不选u，dp[u][1]选u

// 递归处理节点u，fa是父节点
void dfs(int u, int fa) {
// 初始化状态
dp[u][1] = w[u];
dp[u][0] = 0;

// 遍历所有子节点
for (auto v : adj[u]) {
if (v == fa) continue;
dfs(v, u); // 先处理子节点

// 状态转移：合并子节点的结果
dp[u][1] += dp[v][0]; // 选u，子节点必须不选
dp[u][0] += max(dp[v][0], dp[v][1]); // 不选u，子节点选或不选取最大
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n;
cin >> n;
// 输入节点权值
for (int i = 1; i <= n; ++i) {
cin >> w[i];
}
// 输入n-1条边，构建邻接表
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}

// 以1为根节点，父节点为-1
dfs(1, –1);

// 输出最大独立集的权值和
cout << max(dp[1][0], dp[1][1]) << endl;

return 0;
}

/* 测试案例：
输入：
5
1 2 3 4 5
1 2
1 3
2 4
2 5
树结构：
1(1)
/ \\
2(2) 3(3)
/ \\
4(4) 5(5)
计算过程：
– 处理4：dp[4][1]=4, dp[4][0]=0
– 处理5：dp[5][1]=5, dp[5][0]=0
– 处理2：
dp[2][1] = 2 + dp[4][0] + dp[5][0] = 2+0+0=2
dp[2][0] = max(4,0) + max(5,0) = 4+5=9
– 处理3：dp[3][1]=3, dp[3][0]=0
– 处理1：
dp[1][1] = 1 + dp[2][0] + dp[3][0] = 1+9+0=10
dp[1][0] = max(2,9) + max(3,0) = 9+3=12
最终答案：max(10,12)=12
解释：选3、4、5，权值和3+4+5=12，符合独立集要求（无相邻节点）
*/

代码核心解析

新手：为什么必须先处理子节点再合并？反过来不行吗？ 导师：树形DP的核心是“子树的解推导父节点的解”，如果先处理父节点再处理子节点，子节点的状态还未计算，父节点的状态就无法正确合并。比如处理节点2时，必须先知道4和5的dp值，才能计算2的dp值——这和区间DP“从小到大枚举长度”的逻辑本质一致，都是保证“依赖的子问题先求解”。

四、入门例题2：树的直径（最长路径）

新手：树的直径问题也是树形DP的经典应用吧？它的实现和最大独立集有什么不同？ 导师：树的直径（也叫树的最长路径）是指树上任意两个节点之间的最长简单路径，树形DP是求解树的直径的两种核心方法之一（另一种是两次DFS/BFS），且更适合需要同时处理权值的场景。

问题定义

给定一棵带权树（边权或点权，此处以边权为例），求树上任意两点之间的最长路径长度（直径）。

解题思路

完整代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int MAXN = 1e5 + 5;
// 邻接表：pair<子节点v，边权w>
vector<pair<int, int>> adj[MAXN];
long long dp[MAXN]; // dp[u]：u到子树的最长路径
long long ans; // 存储树的直径

// 递归处理节点u，fa是父节点
void dfs(int u, int fa) {
dp[u] = 0; // 初始化：u到自身的路径长度为0
long long max1 = 0, max2 = 0; // 最长、次长路径

for (auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (v == fa) continue;

dfs(v, u); // 递归处理子节点

// 计算u到v子树的路径长度
long long cur = dp[v] + w;
// 更新最长、次长路径
if (cur > max1) {
max2 = max1;
max1 = cur;
} else if (cur > max2) {
max2 = cur;
}
// 更新dp[u]（u到子树的最长路径）
dp[u] = max(dp[u], cur);
}

// 以u为拐点的最长路径 = 最长+次长
ans = max(ans, max1 + max2);
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n;
cin >> n;
// 输入n-1条边（u, v, w）
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}

ans = 0;
dfs(1, –1); // 以1为根

cout << "树的直径：" << ans << endl;

return 0;
}

/* 测试案例：
输入：
5
1 2 2
1 3 3
2 4 4
2 5 5
树结构：
1
/ \\ (3)
(2) / 3
2
/ \\
(4)/ \\(5)
4 5
计算过程：
– 处理4：dp[4]=0，max1=0, max2=0 → ans=0
– 处理5：dp[5]=0，max1=0, max2=0 → ans=0
– 处理2：
子节点4：cur=0+4=4 → max1=4, max2=0
子节点5：cur=0+5=5 → max1=5, max2=4
dp[2] = max(4,5)=5
以2为拐点的路径：5+4=9 → ans=9
– 处理3：dp[3]=0，max1=0, max2=0 → ans=9
– 处理1：
子节点2：cur=5+2=7 → max1=7, max2=0
子节点3：cur=0+3=3 → max1=7, max2=3
dp[1] = max(7,3)=7
以1为拐点的路径：7+3=10 → ans=10
最终答案：10（路径4-2-1-3，长度4+2+3=9；或5-2-1-3，长度5+2+3=10，后者是直径）
*/

核心区别与解析

新手：为什么两次DFS也能求直径，而树形DP更优？ 导师：两次DFS的思路是：

两次DFS的优点是代码更简洁，但仅适用于边权非负的情况；而树形DP不仅能处理边权非负的情况，还能灵活处理点权、带限制的直径（比如路径上节点数不超过k），适用场景更广。

五、进阶例题1：树上背包（分组背包的树形版）

新手：树上背包是树形DP的难点吧？它和普通的分组背包有什么关联？ 导师：树上背包是“树形DP + 分组背包”的结合体，核心是“每个节点的子树对应一组物品，选择子树中的节点相当于选择该组的物品，且组内物品互斥（或有依赖）”。最经典的树上背包问题是“树上选m个节点，要求选的节点构成连通块，求最大权值和”。

问题定义

给定一棵n个节点的树，每个节点有一个权值w[u]，选择恰好m个节点，且选中的节点构成连通块（任意两个选中节点之间的路径上的所有节点都被选中），求最大权值和。

解题思路

完整代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int MAXN = 105; // 节点数通常较小（n≤100），因为O(n²m)复杂度
const int INF = INT_MAX / 2;
vector<int> adj[MAXN];
int w[MAXN];
int dp[MAXN][MAXN]; // dp[u][k]：u子树选k个节点（含u）的最大权值和
int size_[MAXN]; // size_[u]：u子树的节点数

// 递归处理节点u，fa是父节点
void dfs(int u, int fa) {
size_[u] = 1;
// 初始化：选u自己，1个节点
dp[u][1] = w[u];

for (auto v : adj[u]) {
if (v == fa) continue;
dfs(v, u);
size_[u] += size_[v];

// 分组背包：k从大到小枚举，避免重复选
for (int k = size_[u]; k >= 1; —k) {
// x：u原有选x个节点，y = k – x：v子树选y个节点
for (int x = min(k–1, size_[u] – size_[v]); x >= 1; —x) {
int y = k – x;
if (y < 0 || y > size_[v]) continue;
if (dp[u][x] == –INF || dp[v][y] == –INF) continue;
dp[u][k] = max(dp[u][k], dp[u][x] + dp[v][y]);
}
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n, m;
cin >> n >> m;
// 初始化dp为负无穷
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = –INF;
}
}

// 输入节点权值
for (int i = 1; i <= n; ++i) {
cin >> w[i];
}
// 输入边
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}

dfs(1, –1);

// 输出答案：根节点1的子树选m个节点的最大权值和
cout << (dp[1][m] == –INF ? –1 : dp[1][m]) << endl;

return 0;
}

/* 测试案例：
输入：
5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
树结构同最大独立集案例
初始化：
dp[4][1]=4, dp[5][1]=5, dp[2][1]=2, dp[3][1]=3, dp[1][1]=1
处理节点2的子节点4：
size_[2] = 2
k从2到1：
k=2：x=1, y=1 → dp[2][2] = dp[2][1] + dp[4][1] = 2+4=6
处理节点2的子节点5：
size_[2] = 3
k从3到1：
k=3：x=2, y=1 → dp[2][3] = 6+5=11
k=2：x=1, y=1 → dp[2][2] = max(6, 2+5=7)=7
处理节点1的子节点2：
size_[1] = 4
k从4到1：
k=3：x=1, y=2 → dp[1][3] = 1 + 7=8
k=2：x=1, y=1 → dp[1][2] = 1+2=3
处理节点1的子节点3：
size_[1] = 5
k从5到1：
k=3：x=2, y=1 → dp[1][3] = max(8, 3+3=6)=8；x=1, y=2 → 1+(-INF)无效
最终dp[1][3]=8（选1、2、3，权值1+2+3=6；或1、2、4，1+2+4=7；或1、2、5，1+2+5=8；或2、4、5，2+4+5=11？注意要求包含根节点1，所以最大是8）
输出：8
*/

核心难点解析

六、进阶例题2：树形DP的换根法（二次扫描）

新手：有些树形DP问题需要求“每个节点作为根时的最优解”，比如“求每个节点到其他所有节点的距离和”，这该怎么处理？ 导师：这就需要用到“换根DP（也叫二次扫描法）”——核心是“先以任意节点为根做一次DFS，计算子树内的状态；再做一次DFS，将根的状态转移到子节点，得到所有节点作为根的解”。

问题定义

给定一棵带权树（边权为1，即路径长度为节点数），求每个节点u到其他所有节点的距离之和ans[u]。

解题思路

第一步：第一次DFS（自底向上）

第二步：第二次DFS（自顶向下，换根）

完整代码实现（C++）

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
long long dp[MAXN]; // 子树内距离和
long long ans[MAXN]; // 每个节点的总距离和
int size_[MAXN]; // 子树节点数
int n;

// 第一次DFS：自底向上计算dp和size_
void dfs1(int u, int fa) {
size_[u] = 1;
dp[u] = 0;
for (auto v : adj[u]) {
if (v == fa) continue;
dfs1(v, u);
size_[u] += size_[v];
dp[u] += dp[v] + size_[v];
}
}

// 第二次DFS：自顶向下换根计算ans
void dfs2(int u, int fa) {
for (auto v : adj[u]) {
if (v == fa) continue;
// 换根：u→v
ans[v] = ans[u] – size_[v] + (n – size_[v]);
dfs2(v, u);
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}

// 第一次DFS：以1为根
dfs1(1, –1);
ans[1] = dp[1]; // 根节点的总距离和就是dp[1]
// 第二次DFS：换根
dfs2(1, –1);

// 输出每个节点的距离和
for (int i = 1; i <= n; ++i) {
cout << "节点" << i << "的距离和：" << ans[i] << endl;
}

return 0;
}

/* 测试案例：
输入：
5
1 2
1 3
2 4
2 5
树结构同前
第一次DFS（根1）：
– dfs1(4,-1): size_[4]=1, dp[4]=0
– dfs1(5,-1): size_[5]=1, dp[5]=0
– dfs1(2,1): size_[2]=3, dp[2] = (0+1)+(0+1)=2
– dfs1(3,1): size_[3]=1, dp[3]=0
– dfs1(1,-1): size_[1]=5, dp[1] = (2+3)+(0+1)=6 → ans[1]=6
第二次DFS：
– 处理1的子节点2：
ans[2] = 6 – 3 + (5-3) = 6-3+2=5
– 处理1的子节点3：
ans[3] = 6 – 1 + (5-1) = 6-1+4=9
– 处理2的子节点4：
ans[4] = 5 – 1 + (5-1) = 5-1+4=8
– 处理2的子节点5：
ans[5] = 5 – 1 + (5-1) = 8
输出：
节点1的距离和：6
节点2的距离和：5
节点3的距离和：9
节点4的距离和：8
节点5的距离和：8
验证：
节点1的距离：1→2(1),1→3(1),1→4(2),1→5(2) → 1+1+2+2=6 ✔️
节点2的距离：2→1(1),2→3(2),2→4(1),2→5(1) →1+2+1+1=5 ✔️
*/

核心解析

七、树形DP的常见坑点与优化

新手：学习树形DP容易踩哪些坑？有没有通用的优化技巧？ 导师：新手最容易踩的5个坑：

通用优化技巧

八、树形DP的经典应用场景

新手：除了上述例题，树形DP还能解决哪些问题？ 导师：树形DP的应用场景覆盖所有“树结构的最优解/计数问题”，常见场景：

九、总结

核心要点回顾

学习建议

树形DP的核心是“理解树的递归结构+灵活设计状态转移”，建议你：

记住：树形DP的框架是固定的，但状态转移需要根据问题灵活调整——只要想清楚“父节点的状态如何由子节点的状态推导”，就能设计出正确的转移方程。从简单例题入手，逐步攻克复杂场景，你会发现树形DP其实并不难。