🌲 第一关：什么是「树」？
在学 DFS 和 BFS 时，我们搜索的是「图」——节点之间用边连起来，可能有环、可能不连通。而树是一种非常特殊的图，特殊到它有自己的一整套理论和术语。
🌳 树的严格定义：树是一个连通且无环的无向图。
也就是说：任意两个节点之间都能走到（连通），而且没有回路（无环）。
🏠 生活比喻
家谱树：你是你爸妈的孩子，爸妈是爷爷奶奶的孩子……每个人都只有一个「上一代」，不会有「你既是A的孩子又是B的孩子」还形成环的情况。
公司组织架构：CEO 在最上面，下面是各部门总监，再下面是经理、员工。每个人只有一个直接上级，不会出现「A管B，B管C，C又管A」的循环。
文件目录：文件夹里套文件夹，不会有一个文件夹最终又包含自己。
📊 树 vs 普通图，差在哪？
| 对比项 | 普通图 | 树 |
|---|
| 有没有环 | 可能有 | 一定没有 |
| 两点间路径 | 可能有多条 | 恰好一条（唯一路径） |
| 边数 | 任意 | 恰好 n-1 条（n个节点） |
| 连通性 | 可能不连通 | 一定连通 |
| 断一条边 | 可能还连通 | 一定变成两棵树（断开） |
💡 一个超有用的等价说法：下面 5 句话互相等价，满足任意一条就是树——
① 连通且无环 ② 连通且有 n-1 条边 ③ 无环且有 n-1 条边 ④ 任意两点间恰有一条路径 ⑤ 连通，且删掉任意一条边就不连通了
🔍 判断练习：下面哪些是树？
❌ 不是树（有环：50→100→150→100→50 形成回路）
📚 第二关：树的术语词典
做树的题目，先得认识这些词。下面这张图标注了所有常用术语，鼠标悬停或点击节点可以高亮它的角色。
👆 点击树上的任意节点，查看它的术语角色
根节点 (root)
树最顶端的节点，没有父节点。一棵树只有一个根。
叶子节点 (leaf)
没有子节点的节点，长在树的最底端。
父节点 (parent)
某个节点往上一层的直接邻居（在根的方向）。
子节点 (child)
某个节点往下一层的直接邻居。
深度 (depth)
从根到该节点的边数。根的深度是 0。
层 (level)
深度相同的所有节点在同一层。第 0 层只有根。
边 (edge)
连接两个节点的线。n 个节点的树有 n-1 条边。
度 (degree)
一个节点的子节点数量。叶子的度是 0。
⚠️ 注意：「父/子」和「深度」都依赖于你选哪个节点当根。同一棵树，选不同节点当根，父子和深度的关系会变！但「两点间的路径」和「距离」不会变。
💎 第三关：树的五大黄金性质
这五条性质几乎出现在每一道树题里，必须刻在脑子里。
1唯一路径定理
树上任意两个节点之间，有且仅有一条路径。
为什么重要：这是 P11962 的根基！因为路径唯一，所以两点间的距离是确定的，奇偶性也是确定的——这才能用「染色」一招解决。
2边数定理
n 个节点的树，恰好有 n-1 条边。
直觉理解：第一个节点是孤立的，每加一条边就多连一个节点进来。要连 n 个节点，正好需要 n-1 条边。多一条就有环，少一条就不连通。
3无环定理
树里没有任何环（回路）。从任意节点出发，不可能走一圈回到自己。
推论：在树上做 DFS/BFS 时，不需要 visited 数组防环！只需要记住「从哪个父节点来的」，不往回走就行。这让树上遍历比图上简单得多。
4二分图定理（⭐ 核心中的核心）
树一定是二分图：可以把所有节点染成两种颜色，使得每条边连接的两个节点颜色不同。
染色方法：从根开始，根染紫色（第0层），它的孩子染绿色（第1层），孙子又染紫色（第2层）……交替染色。
为什么树一定能染成功？因为树没有奇数长度的环（根本没有环！），不会出现「绕一圈回来颜色矛盾」的情况。普通图如果有奇环就染不了。
5断边定理
删掉树上的任意一条边，树会断成两棵不连通的树。
对比：普通图删一条边可能还连通（有别的路绕过去）。但树的唯一路径意味着没有「备选路线」，断一条就彻底分家。
🌉 记住这五条，P11962 的解法就自然浮现了：
性质1（唯一路径）→ 距离确定 → 奇偶性确定
性质4（二分图）→ 可以染色 → 同色=偶距离，异色=奇距离
两条合起来 → 答案只跟颜色有关 → O(n) 搞定！
💾 第四关：树的存储与遍历
📦 怎么存一棵树？
树是无向图，用邻接表存最方便。每条边存两次（两个方向）。
📄 点击展开：建树代码
▶
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> adj[N]; // 邻接表
int main() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) { // 树有 n-1 条边
int u, v;
cin >> u >> v;
adj[u].push_back(v); // 双向存
adj[v].push_back(u);
}
// 接下来遍历...
return 0;
}
🚶 树上 DFS：不需要 visited！
关键区别：在图上做 DFS 必须有 visited 数组防环。但树没有环，只需要传一个 parent（父节点）参数，避免「往回走到父节点」就行！
// 树上 DFS：传 parent 防止回头，不需要 visited 数组
void dfs(int u, int parent) {
for (int v : adj[u]) {
if (v != parent) { // 不往父节点走
dfs(v, u); // 递归，u 是 v 的父
}
}
}
// 调用：从根节点 1 开始，父节点设为 0（不存在）
dfs(1, 0);
💡 对比图上的 DFS：
图上：if (!visited[v]) { visited[v] = true; dfs(v); }
树上：if (v != parent) { dfs(v, u); }
少一个数组，少一步标记，简单清爽！
🌊 树上 BFS：分层遍历
树上的 BFS 就是层序遍历——一层一层往下走。同样不需要 visited，用 parent 就行。
// 树上 BFS（层序遍历）
queue<int> q;
int depth[N]; // 记录每个节点的深度
q.push(1); // 根节点入队
depth[1] = 0; // 根的深度是 0
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (v != parent_of[u]) { // 不回头
depth[v] = depth[u] + 1; // 深度 = 父深度 + 1
q.push(v);
}
}
}
🎯 depth 数组就是天然的染色！
depth[v] % 2 == 0 → 偶数层（紫色）
depth[v] % 2 == 1 → 奇数层（绿色）
这就是 P11962 里 BFS 染色的来历——depth 的奇偶性 = 颜色！
🎨 第五关：BFS 分层染色动画
来看一棵 8 个节点的树，BFS 从根节点 1 出发，一层一层染色。偶数层染紫色，奇数层染绿色。
点击「播放」开始 BFS 分层染色
速度：
中速
👀 观察重点：每一步处理的节点和它的父节点颜色一定不同。这就是二分图染色的过程！
动画结束后，数一下紫色和绿色各有多少个——这就是 P11962 的两个答案值。
🛤️ 第六关：唯一路径演示
树上两点之间只有一条路径。点击两个节点（先点起点，再点终点），系统会画出这条唯一路径，并告诉你路径长度和奇偶性。
👆 先点击一个节点作为起点，再点击另一个节点作为终点
🎯 发现规律了吗？
• 路径长度是偶数 → 起点和终点同色
• 路径长度是奇数 → 起点和终点异色
这不是巧合！每走一步颜色变一次，走偶数步回到同色，走奇数步变成异色。多试几组验证这个规律！
🌉 第七关：从树到树上漫步
现在把前面学的全部串起来，看 P11962 的思路是怎么一步步「长出来」的。
第 1 步：题目要什么？
从每个节点出发，走偶数步能到达哪些节点？对所有 n 个节点都要求答案。
第 2 步：暴力为什么不行？
对每个节点做 BFS 算距离 → O(n²)，n=2×10⁵ 时 4×10¹⁰ 次运算，1 秒跑不完，TLE。
第 3 步：用树的性质 1（唯一路径）
树上两点间路径唯一 → 距离确定 → 奇偶性确定。
「偶数步能到达」等价于「距离是偶数」。
（为什么绕路也不改变奇偶性？走过去再走回来 +2 步，奇偶不变）
第 4 步：用树的性质 4（二分图）
树可以双色染色 → 偶数层一色，奇数层另一色。
走偶数步 = 颜色变偶数次 = 回到同色。
所以「距离是偶数」=「同色」！
第 5 步：最终结论
• 紫色节点的答案 = 紫色节点的总数 cnt[0]
• 绿色节点的答案 = 绿色节点的总数 cnt[1]
只需一次 BFS 染色，O(n) 搞定！
📋 完整知识链条
| 环节 | 知识点 | 在本教程的哪一关 |
|---|
| 树是什么 | 连通无环图 | 第1关 |
| 路径唯一 | 性质1：唯一路径 | 第3关 + 第6关演示 |
| 距离确定 | 路径唯一→距离确定→奇偶确定 | 第6关 |
| 可以染色 | 性质4：树是二分图 | 第3关 + 第5关动画 |
| 同色=偶距离 | 走一步颜色变一次 | 第6关规律 |
| 答案只看颜色 | cnt[0] 和 cnt[1] | 第7关桥接 |
| 代码实现 | BFS + depth奇偶 | P11962 教程第5关 |
🎯 第八关：互动测验
8 道题，检验你对树的掌握。全对就可以冲 P11962 了！