GESP 六级备考 · 从零理解树的所有核心概念
在学 DFS/BFS 的时候，你已经在树上做过搜索了。但"树"到底有哪些性质？这一节我们从零开始，把树的核心概念一次讲清楚。
树（Tree）是一种特殊的有向/无向图，它满足：
1. 连通：任意两个节点之间都有路径相连
2. 无环：没有回路，不会绕一圈走回来
3. n 个节点，n-1 条边：这是树的标志性性质
如果你去掉一条边，树就会变成两棵更小的树（断开连通）；如果加一条边，就会出现环（不再无环）。所以 n-1 条边恰好是"连通且无环"的黄金数量。
下面这些术语在所有树相关题目中都会反复出现。先看一遍定义，然后在互动树里亲手感受。
点击树上的任意节点，右侧面板会显示它的深度、度数、父节点和子节点。试着找出根节点、叶子节点，看看不同节点的属性有什么不同。
点击树上的任意节点查看属性
1. 树中任意两个节点之间有且仅有唯一路径（因为没有环）。
2. 这条唯一路径的长度 = 两点之间的距离。
3. 选不同的根节点，树的"形状"会不同，但边的连接关系不变。这叫做有根树 vs 无根树。
4. 竞赛中最常用的存储方式是 邻接表：vector<int> adj[MAXN]，每条边存两次（双向）。
const int MAXN = 200005; vector<int> adj[MAXN]; // 邻接表 // 读入 n-1 条边 for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); // 双向存边 adj[v].push_back(u); }
树的遍历就是按某种顺序访问所有节点。不同的遍历方式，访问顺序不同，用途也不同。下面用同一棵树，对比四种遍历方式。
访问顺序：根 → 左子树 → 右子树
先访问根节点，然后递归遍历左子树，最后递归遍历右子树。这是最"自然"的 DFS 顺序。
用途：复制一棵树、输出目录结构、表达式树的前缀表达式（波兰表达式）。
| 遍历方式 | 访问顺序 | 核心特点 | 典型用途 |
|---|---|---|---|
| 前序 | 根 → 左 → 右 | 根在第一个 | 复制树、目录结构 |
| 中序 | 左 → 根 → 右 | 根在中间 | 二叉搜索树排序 |
| 后序 | 左 → 右 → 根 | 根在最后 | 删除树、子树计算 |
| 层序 | 逐层从左到右 | BFS 方式 | 求深度、最短路径 |
void dfs(int u, int fa) { // 前序：在这里访问 u（根→左→右） visit(u); for (int v : adj[u]) { if (v != fa) { // 不走回头路 dfs(v, u); } } // 后序：在这里访问 u（左→右→根） } void bfs(int root) { // 层序遍历 queue<int> q; q.push(root); while (!q.empty()) { int u = q.front(); q.pop(); visit(u); for (int v : adj[u]) if (!vis[v]) { vis[v] = true; q.push(v); } } }
在无根树（邻接表存储）上做 DFS 时，需要传入 fa（父节点）参数，避免"走回头路"。这是树上 DFS 最重要的模板，几乎所有树题都会用到。
如果是有根树（每个节点知道自己的子节点列表），则不需要 fa，直接遍历 children[u] 即可。
树上很多问题都需要用到递归：先解决子问题（子树），再把结果合并到当前节点。这种"自底向上"的思考方式是树形 DP 的基础。
选一个根节点后，对于树上任意节点 u，子树(u) 包含 u 本身以及 u 的所有后代节点。如果 u 是叶子，它的子树只有自己。
定义：size[u] = 以 u 为根的子树中节点的个数（包括 u 自身）。
递推：size[u] = 1 + sum(size[v])，其中 v 是 u 的所有子节点。
边界：叶子节点的 size = 1。
这就是典型的"后序遍历"思想——先算子节点，再算自己。
点击"播放"，看 DFS 如何从叶子开始，自底向上计算每个节点的子树大小。注意右侧的递归调用栈，它展示了递归的"深度"。
int size[MAXN]; void calcSize(int u, int fa) { size[u] = 1; // 先算上自己 for (int v : adj[u]) { if (v != fa) { calcSize(v, u); // 递归计算子节点 size[u] += size[v]; // 累加子树大小 } } } // 调用：calcSize(1, 0); // 此时 size[1] = n（整棵树的大小）
同样的"后序递推"模式可以解决很多子树问题：
1. 子树最大值：mx[u] = max(val[u], max(mx[v]))
2. 子树节点和：sum[u] = val[u] + sum(sum[v])
3. 子树深度：h[u] = 1 + max(h[v])（叶子 h=1）
4. 子树中满足条件的节点数：根据条件调整递推关系
核心模板都是：先递归子节点，再合并结果到当前节点。
树上任意两点之间有唯一路径。理解这条路径，是解决很多树题的关键。最近公共祖先（LCA）是这条路径上的关键枢纽。
对于节点 u 和 v，它们的 LCA(u, v) 是同时是 u 和 v 祖先的节点中，深度最大的那个（离 u、v 最近的）。
想象一棵家谱树，你是节点 u，你朋友是节点 v。你们的 LCA 就是你们最近的共同祖先——可能是你们的爷爷，也可能是更上面的人。
特例：如果 u 是 v 的祖先，那么 LCA(u, v) = u。
点击树上的两个节点，系统会高亮它们的路径，并标出 LCA。观察路径的走向：它从 u 上行到 LCA，再从 LCA 下行到 v。
点击树上的两个节点
因为树上任意两点之间有唯一路径，所以距离 = 路径长度。而路径一定经过 LCA：
dist(u, v) = depth[u] + depth[v] - 2 * depth[LCA]
解释：u 到 LCA 的距离 = depth[u] - depth[LCA]，LCA 到 v 的距离 = depth[v] - depth[LCA]。加起来就是：
(depth[u] - depth[LCA]) + (depth[v] - depth[LCA]) = depth[u] + depth[v] - 2*depth[LCA]
回到 P11962 树上漫步：偶数步能到达 ⟺ 距离为偶数 ⟺ depth[u] + depth[v] - 2*depth[LCA] 为偶数。
而 2*depth[LCA] 一定是偶数，所以距离的奇偶性只取决于 depth[u] + depth[v] 的奇偶性，即 depth[u] 和 depth[v] 奇偶性相同。
这就是为什么"偶数步到达 ⟺ 深度奇偶性相同"——LCA 是理解这个结论的关键一步！
1. 先 BFS 求出每个节点的深度和父节点。
2. 把 u 和 v 中较深的那个向上走，直到和另一个一样深。
3. 两个一起向上走，直到相遇——相遇点就是 LCA。
时间复杂度 O(n) 每次查询。适合 n 较小的题。
int depth[MAXN], parent[MAXN]; void bfs(int root) { // BFS 求深度和父节点 queue<int> q; q.push(root); depth[root] = 0; parent[root] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) if (v != parent[u]) { parent[v] = u; depth[v] = depth[u] + 1; q.push(v); } } } int lca(int u, int v) { while (depth[u] > depth[v]) u = parent[u]; // 深的先走 while (depth[v] > depth[u]) v = parent[v]; while (u != v) { u = parent[u]; v = parent[v]; } // 一起走 return u; }
对于 n 很大的题（如 n ≤ 2×10^5，q ≤ 10^5 次查询），朴素法 O(n) 每次查询太慢。倍增法预处理 O(n log n)，每次查询 O(log n)。
核心思想：让 fa[u][k] 表示 u 向上走 2^k 步到达的节点。利用二进制分解，把"向上走 d 步"变成 log d 次跳跃。
这是 GESP 六级以上的进阶内容，理解朴素法后再学倍增会轻松很多。
1. 树的定义：连通无环图，n 个节点 n-1 条边，任意两点唯一路径
2. 树的概念：根、叶子、父/子、深度、高度、度——选根后这些才有意义
3. 四种遍历：前序（根→左→右）、中序（左→根→右）、后序（左→右→根）、层序（BFS）
4. 子树递归：先递归子节点，再合并到当前节点——后序遍历的思想
5. LCA：两节点最近公共祖先，是树上路径的枢纽
6. 树上距离：dist(u,v) = depth[u] + depth[v] - 2*depth[LCA]
1. 先掌握邻接表建树和DFS 遍历模板（fa 参数），这是所有树题的基础。
2. 理解后序遍历的"先子后根"思想，这是子树计算和树形 DP 的核心。
3. 把 LCA 和树上距离公式记住，很多树题都间接用到这个公式。
4. 回到"树上漫步"：现在你应该能完整理解为什么偶数步到达 ⟺ 深度奇偶性相同了——它就是 LCA 距离公式的直接推论。
1. 树的遍历（模板题）→ 2. 子树大小计算 → 3. 树上漫步 P11962（深度奇偶性）→ 4. LCA 模板题 → 5. 倍增 LCA → 6. 树形 DP 入门
每一步都建立在前一步的基础上。不要跳步，扎扎实实走完这条线，树相关的题就不再可怕了。