本讲定位：图论系列第十一讲。前十讲把树当成”一种特殊的图”顺手用过好几次（第 04 讲的拓扑序、第 10 讲的最小生成树），本讲开始把树当成研究对象。三样东西：DFS 序（把树拍平成一个序列，“子树 = 一段连续区间”是后面所有树上数据结构的地基）、树的直径、树的重心。做了六组实测，三个数字值得先记住：“两次 BFS 求直径”在边权可负时错 8.59%，最小反例只要 4 个点——而这个前提几乎从不被写进口诀里；求重心时忘了”上面那一块”（
n - siz[u]）实测错 91.77%；以及”子树对应 DFS 序上一段连续区间”这条结论在 20 000 组随机树上零违反（这是本讲唯一需要你无条件相信的结论，所以专门验了一遍）。另外顺手量了递归 DFS 求 DFS 序的爆栈线：8 MB 栈下约 17 万层。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，B4016、P1364 与洛谷官方样例核对通过。前置知识：第 01 讲（邻接表存图）、第 02 讲（DFS/BFS 的性质，尤其递归爆栈那一节——本讲第 2.3 节是它的第三次出场）。不需要最短路和最小生成树，第 05～10 讲没跟上也可以直接学本讲。第 10 讲第 7～9 节挂着的三道题（P1967、P4180、MST 唯一性判定）要等下一讲的 LCA 才能补齐，本讲先把树的基础打好。
适合对象：第 1、2、3 节标 J（DFS 序是 CSP-J 复赛的隐形前置，很多题的”子树修改/子树查询”都靠它）；第 4 节直径的两次 BFS 法标 J、树形 DP 法标 J⭐、4.6 节的两条性质标 S；第 5 节重心标 J⭐ / S。
第 01 讲给过一句话：“树是特殊的图”。现在把它说准确。
对一个 $n$ 个点的无向图，下面五句话两两等价——任意一句成立，其余四句自动成立：
- 它是树（连通且无环）；
- 连通，且恰好 $n-1$ 条边；
- 无环，且恰好 $n-1$ 条边；
- 任意两点之间存在且仅存在一条简单路径；
- 它连通，且删掉任意一条边就不连通（每条边都是桥，见第 14 讲）。
做题时最常用的是第 2、4 条：第 2 条用来一眼认出”这是棵树”（看到 $n$ 个点 $n-1$ 条边且保证连通，别再想一般图的算法）；第 4 条是本讲和下一讲的全部基础——
“任意两点之间路径唯一” 意味着”$u$ 到 $v$ 的路径”是一个确定的对象，可以谈它的长度、它上面的最大边、它经过了哪些点。在一般图里这些问法都要加”最短的那条”才有意义。
给树定一个根（随便选，一般选 1 号点）之后，就有了父亲、儿子、深度、子树、祖先这一整套词汇。注意”根”是我们自己加的——题目给的树通常是无根的（第 5 节的重心、第 4 节的直径都与根无关），但算法几乎总是要先定一个根，因为只有定了根才能递归。
fa、dep、sizint fa[N], dep[N], siz[N];
void dfs(int u, int p) {
fa[u] = p; dep[u] = dep[p] + 1; siz[u] = 1; // dep[根] = 1（dep[0] = 0）
for (int v : g[u]) {
if (v == p) continue; // 无向图存了两条边，别往回走
dfs(v, u);
siz[u] += siz[v]; // 回溯时累加，这叫「后序」
}
}
三个量的求法位置不一样，值得记清楚：
| 量 | 在什么时候算 | 叫什么 |
|---|---|---|
fa[u]、dep[u] |
进入 $u$ 时（用父亲的信息） | 先序（自上而下） |
siz[u] |
离开 $u$ 时（用儿子的信息） | 后序（自下而上） |
“哪些信息自上而下传、哪些自下而上收”是所有树上算法的第一个分水岭。 深度、到根的距离、路径上的最大值是先序；子树大小、子树和、子树最深深度是后序。树形 DP 绝大多数是后序（见
dp-series/05-tree-dp.md），树上差分的还原是后序（下一讲）。
if (v == p) continue 这一行不能漏。 无向图的邻接表里每条边存了两遍，不判父亲就会在两点之间来回递归。注意它只在树上够用——一般图要用 vis 数组（第 02 讲）；而如果树上有重边（题目允许的话），判父亲编号就不够了，要改成判边的编号（这个技巧在第 14 讲判桥时是必须的）。
题目往往只给你 $n-1$ 条边，不告诉你根。直接 dfs(1, 0) 就行——选哪个点当根不影响 siz 之外的结论，而 siz 本身的含义就依赖于根，这是正常的。