0什么是树？
树不是「长在地上的植物」，而是一种特殊的图。它长这样（下面这棵就是本课的演示树，9 个点）：
树的三个定义（满足任意两个就能推出第三个）
- ① 连通：任意两个点之间都有路可走（没有「孤岛」）。
- ② 无环：任何地方都没有「圈圈」（没有绕一圈回到原点的路）。
- ③ n 个点恰好 n−1 条边。
🔍 判定小测试：下面这些图，哪些是树？（点选项看对错）
① 这个图是树吗？（3 个点 3 条边，围成三角形）
② 一条链（4 个点 3 条边排成一行）呢？
③ 一颗星星（中心 + 3 片叶子，4 点 3 边）？
④ 两个分开的三角形（6 个点 6 条边）？
⑤ 一个正方形（4 点 4 边围成圈）？
1树的术语（点一点就懂）
我们可以任选一个点当「根」（就像把树拎起来）。选 1 号点当根后，每个点就有了爸爸、孩子、深度这些身份。点击下面树上的任意节点，看它的「身份档案」！
| 术语 | 意思 | 在这棵树上 |
|---|---|---|
| 根 | 我们选来「挂」整棵树的点 | 1 |
| 父节点 / 孩子 | 深度差 1、直接相连、往根的方向是父 | 2 的父是 1，2 的孩子是 4、5 |
| 叶子 | 没有孩子的节点 | 4、7、8、9 |
| 深度 | 到根的距离（根 = 0） | 5 的深度是 2 |
| 祖先 | 自己到根路径上的点（不含自己） | 8 的祖先是 5、2、1 |
| 子树 | 自己 + 所有后代 | 2 的子树是 {2,4,5,7,8} |
2树的存储：邻接表
程序里怎么存树？最常用邻接表：每个点开一个列表，记下所有和它相连的点。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> g[N]; // g[u] 里存所有和 u 相连的点（邻居）
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) { // 树有 n-1 条边
int u, v;
cin >> u >> v;
g[u].push_back(v); // u 和 v 相连
g[v].push_back(u); // 无向，双向都记
}
// 例：输出节点 2 的所有邻居
for (int i = 0; i < (int)g[2].size(); i++) cout << g[2][i] << " ";
return 0;
}lc[i]、rc[i] 两个数组存左右孩子，更省空间。3树的遍历：DFS 前序 & BFS 层序
遍历 = 把每个点都走一遍。两种走法都要会（GESP 六级直接考）：
- 前序遍历（DFS 递归）：先访问自己，再访问孩子，一个孩子的整棵子树走完才轮到下一个。
- 层序遍历（BFS 队列）：先访问第 0 层，再第 1 层……一层一层从左到右。
动画①：前序遍历（DFS）
动画②：层序遍历（BFS）
颜色深浅 = 层数，越远越暖色。队头出队，把孩子入队，波纹式扩散。
代码对照
// 前序遍历（DFS 递归）：先自己，再孩子
void preorder(int u, int fa) {
cout << u << " "; // 访问自己
for (int v : g[u]) {
if (v == fa) continue; // 别走回爸爸
preorder(v, u); // 递归访问孩子
}
}
// 层序遍历（BFS 队列）：一层一层
void levelorder() {
queue<int> q;
q.push(1); // 根入队
vis[1] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " "; // 访问自己
for (int v : g[u]) {
if (vis[v]) continue;
vis[v] = true;
q.push(v); // 孩子入队
}
}
}depth[v] = depth[u] + 1 加进上面的代码，一次遍历就得到所有点的深度——非常常用，一定要记住！4深度与染色：树是「二部图」
给树染两种颜色：偶数深度的点染蓝色，奇数深度的点染橙色。你马上会发现一个超强规律。
5路径与距离：LCA 的魔法公式
树上两点 u、v 的距离怎么算？先找到它们的最近公共祖先（LCA，Lowest Common Ancestor）——就是离它们俩都最近的公共祖先。然后套公式：
dist(u,v) = depth[u] + depth[v] − 2 × depth[LCA(u,v)]
👇 玩法：先点一个节点（绿色=起点），再点第二个节点（红色=终点），路径会亮起来，公式也会自动代入数字算给你看！
朴素 LCA 代码（一步一步往上爬）
// 前提：depth[] 和 fa[]（爸爸）已经算好了
int lca(int u, int v) {
while (depth[u] > depth[v]) u = fa[u]; // 深的先往上爬到同一层
while (depth[v] > depth[u]) v = fa[v];
while (u != v) { // 再一起往上爬
u = fa[u];
v = fa[v];
}
return u; // 相遇点就是 LCA
}
// 距离公式
int dist = depth[u] + depth[v] - 2 * depth[lca(u, v)];6综合小测验
1️⃣ 一棵有 7 个节点的树，一共有几条边？
2️⃣ 树上两个不同点之间，有几条不重复走点的路径？
3️⃣ 判断题：任何树都可以用两种颜色染好，让相邻节点不同色。
4️⃣ 本课演示树中（以 1 为根），depth[5]=2，depth[9]=3。节点 5 和 9 的距离是？
5️⃣ 两个节点的深度同为偶数，它们的距离是？
6️⃣ 树去掉任意一条边，会发生什么？
7总结 & 下一步
| 知识点 | 一句话 | 用在哪 |
|---|---|---|
| 树的定义 | 连通 + 无环 = n 点 n−1 边 | 读题识别树 |
| 邻接表 | vector<int> g[N]，双向存边 | 建树 |
| DFS 前序 | 先自己再孩子，递归 | 求 depth、fa、子树大小 |
| BFS 层序 | 队列一层层走 | 求 depth、最短路 |
| 深度与染色 | 深度奇偶翻转染色，树是二部图 | 判断两点能否偶数步到达 |
| 距离公式 | dist = depth[u]+depth[v]−2×depth[LCA] | 判断偶数步可达 |
如果这一课玩熟了，下一课可以挑战：树的直径（最远的两点有多远）、树的重心（把树切在哪最平衡），还有倍增 LCA（七级内容）。想学哪个，跟我说！