08 树上问题入门
2026-06-30 18:58:47
发布于：广东
2阅读
0回复
0点赞
08 树上问题入门
一、本阶段目标
学完本阶段，学生要能做到：
1. 理解树是一种特殊的图。
2. 会用 DFS 遍历树。
3. 会求父节点、深度、子树大小。
4. 会求树的高度和直径。
5. 初步理解树形 DP 的“从子树合并答案”。
二、什么是树
树是一张满足以下条件的无向图：
1. 连通。
2. 没有环。
如果有 n 个点，那么树一定有：
n - 1 条边
树上任意两点之间有且只有一条简单路径。
三、树与普通图的区别
| 内容 | 普通图 | 树 |
|---|---|---|
| 是否可能有环 | 可能 | 不可能 |
| 两点之间路径 | 可能多条 | 恰好一条 |
| 边数 | 不固定 | n-1 |
| DFS 是否需要 vis | 通常需要 | 可用父节点 fa 防止回头 |
四、树的邻接表存储
vector<int> g[N];
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
五、树的 DFS 模板
void dfs(int u, int fa) {
parent[u] = fa;
for (int v : g[u]) {
if (v == fa) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
这里用 fa 表示父节点，避免从儿子走回父亲。
六、求深度
depth[root] = 1;
dfs(root, 0);
含义：
depth[u] = u 到根的边数 + 1
如果希望根深度为 0，也可以：
depth[root] = 0;
保持全程统一即可。
七、求子树大小
void dfs(int u, int fa) {
siz[u] = 1;
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
含义：
siz[u] = 以 u 为根的子树中有多少个点
这体现了树上递归的核心思想：
先算完儿子，再合并到父亲。
八、求树的高度
树的高度可以看作根到最深叶子的距离。
int height(int u, int fa) {
int h = 0;
for (int v : g[u]) {
if (v == fa) continue;
h = max(h, height(v, u) + 1);
}
return h;
}
九、树的直径
树的直径：树上距离最远的两个点之间的距离。
常用方法：两次 BFS/DFS。
步骤：
1. 从任意点出发，找到最远点 A。
2. 从 A 出发，再找到最远点 B。
3. A 到 B 的距离就是树的直径。
为什么成立可以直观理解：
从任意点向外走到最远处，一定会到达某条最长路径的端点之一。
再从这个端点出发，能找到另一端。
十、树的直径 BFS 模板
pair<int, int> bfs(int s, int n) {
vector<int> dist(n + 1, -1);
queue<int> q;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
int id = s;
for (int i = 1; i <= n; i++) {
if (dist[i] > dist[id]) id = i;
}
return {id, dist[id]};
}
int main() {
auto [a, d1] = bfs(1, n);
auto [b, diameter] = bfs(a, n);
cout << diameter << '\n';
}
十一、简单树形 DP
树形 DP 通常遵循：
先处理子节点
再用子节点结果更新当前节点
典型模型：树上最大独立集。
题意：树上每个点有权值，选一些点，使得不能同时选父子，最大权值是多少。
状态：
dp[u][0]：不选 u 时，u 子树内最大权值
dp[u][1]：选 u 时，u 子树内最大权值
转移：
如果选 u，那么所有儿子都不能选：
dp[u][1] += dp[v][0]
如果不选 u，那么儿子可选可不选：
dp[u][0] += max(dp[v][0], dp[v][1])
代码：
void dfs(int u) {
dp[u][1] = val[u];
for (int v : child[u]) {
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
这是提高内容，零基础学生只需要理解“选/不选”状态即可。
十二、课堂例题
例题 1：求每个点深度
从根开始 DFS。
儿子深度 = 父亲深度 + 1。
例题 2：求子树大小
siz[u] = 1 + 所有儿子的 siz 之和。
例题 3：树的直径
两次 BFS/DFS。
例题 4：没有上司的舞会
树形 DP：每个点选或不选。
十三、练习题
| 题号 | 题名 | 训练点 | 建议 |
|---|---|---|---|
| P4913 | 深基16.例3 二叉树深度 | 树高 | 必做 |
| P1030 | 求先序排列 | 二叉树遍历 | 必做 |
| P1305 | 新二叉树 | 树遍历 | 必做 |
| P1352 | 没有上司的舞会 | 树形 DP 入门 | 提高 |
| P2015 | 二叉苹果树 | 树形 DP + 背包 | 冲刺 |
| P2196 | 挖地雷 | DAG/树状路径 DP | 提高 |
链接：
https://www.luogu.com.cn/problem/P4913
https://www.luogu.com.cn/problem/P1030
https://www.luogu.com.cn/problem/P1305
https://www.luogu.com.cn/problem/P1352
https://www.luogu.com.cn/problem/P2015
https://www.luogu.com.cn/problem/P2196
十四、本阶段作业
- 写出树的 DFS 模板。
- 完成 P4913。
- 写一段代码求所有点深度和父节点。
- 自造一组树，手算子树大小，再用程序验证。
- 选做 P1352，写出 dp 状态定义。
十五、本阶段小结
树上问题关键词：
父节点
深度
子树
叶子
直径
从儿子合并到父亲
树是图论和 DP 的桥梁。深圳自招基础阶段掌握树的 DFS、子树大小、直径即可；强学生再进一步学习 LCA 和树形 DP。
这里空空如也
有帮助，赞一个