树的重心、直径、DFS 序与欧拉序
树是竞赛中最常见的结构,而"重心、直径、DFS 序、欧拉序"是处理树上问题的四把钥匙。2025 年 CSP-S 真题「社团招新」就考了 DFS 序的应用,属于当前命题的热点方向。
一、树的重心
定义:删除某个节点后,树上最大的连通块节点数最小,这个节点叫重心。
一棵树的重心最多有两个(且相邻)。
求法
任选根做一次 DFS,求出每个节点的子树大小 sz[u]。对节点 u,删掉它之后,最大的连通块是:
max( 每个儿子的 sz[son], n - sz[u] )
其中 n - sz[u] 是"父节点那一侧"的节点数。
int sz[N], centroid = 0, bestPart = INF;
void dfs(int u, int fa) {
sz[u] = 1;
int mx = 0;
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
mx = max(mx, sz[v]); // 儿子侧最大的块
}
mx = max(mx, n - sz[u]); // 父节点侧
if (mx < bestPart) { bestPart = mx; centroid = u; }
}
性质
- 以重心为根时,每棵子树的大小都 ≤ n/2
- 重心到所有节点的距离之和最小
- 两个重心的处理:若
n - sz[u] == sz[son],则有两个重心
二、树的直径
定义:树上最长的简单路径长度(边数或边权和)。
求法一:两遍 DFS(只能处理非负边权)
- 任取一点 p,DFS 找到距离 p 最远的点 a
- 从 a 再 DFS,找到距离 a 最远的点 b
- a 到 b 的路径就是直径
pair<int, long long> dist[N]; // 距离 + 走到的点
void dfsFar(int u, int fa, long long d, int& farNode, long long& farDist) {
if (d > farDist) { farDist = d; farNode = u; }
for (auto& e : g[u]) {
if (e.to == fa) continue;
dfsFar(e.to, u, d + e.w, farNode, farDist);
}
}
// 求直径
int a, b;
long long d1 = -1, d2 = -1;
dfsFar(1, 0, 0, a, d1);
dfsFar(a, 0, 0, b, d2);
cout << d2; // 直径长度
求法二:树形 DP(支持负边权)
int ans = 0;
int dfs(int u, int fa) {
int mx1 = 0, mx2 = 0; // 向下最长的两条链
for (int v : g[u]) {
if (v == fa) continue;
int d = dfs(v, u) + 1;
if (d > mx1) { mx2 = mx1; mx1 = d; }
else if (d > mx2) mx2 = d;
}
ans = max(ans, mx1 + mx2); // 经过 u 的最长路径
return mx1;
}
两遍 DFS 法要求边权非负,有负权时必须用树形 DP。
三、DFS 序
定义:对树做一次 DFS,按首次访问的顺序给每个节点编号,得到长度为 n 的序列。
int tin[N], tout[N], timer = 0;
void dfs(int u, int fa) {
tin[u] = ++timer; // 进入时间戳
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
}
tout[u] = timer; // 离开时的时间戳
}
核心性质
子树在 DFS 序中是一段连续区间:[tin[u], tout[u]] 恰好包含 u 的整棵子树。
这条性质极其重要,它把"子树问题"变成了"区间问题":
| 子树操作 | 转成序列操作 |
|---|---|
| 给子树所有节点加值 | 区间加 [tin[u], tout[u]] |
| 查询子树和 | 区间求和 [tin[u], tout[u]] |
| 查询子树第 k 大 | 区间第 k 大 |
配合线段树或树状数组,就能在 O(log n) 内完成子树操作。
// 例子:树状数组维护子树的某些信息
// 建树时按 DFS 序把初始值放进数组
for (int u = 1; u <= n; u++)
bitUpdate(tin[u], value[u]);
// 给 u 的子树全部加 x
rangeAdd(tin[u], tout[u], x);
// 查询 u 的子树和
long long ans = rangeSum(tin[u], tout[u]);
LCA 的位置关系也很有意思:u 是 v 的祖先 ⟺ tin[u] <= tin[v] && tout[v] <= tout[u]。
bool isAncestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
四、欧拉序
定义:DFS 经过节点时记录,每次进入和离开都记录一次,得到长度为 2n-1 的序列。
vector<int> euler; // 欧拉序
int firstPos[N]; // 每个节点首次出现的下标
void dfs(int u, int fa) {
firstPos[u] = euler.size();
euler.push_back(u); // 进入时记录
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
euler.push_back(u); // 返回时再记录一次
}
}
与 DFS 序的区别
| 项目 | DFS 序 | 欧拉序 |
|---|---|---|
| 长度 | n | 2n-1 |
| 记录时机 | 首次进入 | 进入 + 返回都记 |
| 子树 | 连续区间 | 不连续,但每次进入到离开之间是一个区间 |
| 主要用途 | 子树转区间、祖先判断 | LCA 的 RMQ 解法、树上路径 |
用欧拉序求 LCA
在欧拉序中,从 u 首次出现到 v 首次出现之间,深度最小的节点就是 LCA。
void dfs(int u, int fa, int d) {
depth[u] = d;
firstPos[u] = euler.size();
euler.push_back(u);
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u, d + 1);
euler.push_back(u);
}
}
int lca(int u, int v) {
int l = min(firstPos[u], firstPos[v]);
int r = max(firstPos[u], firstPos[v]);
int best = l;
for (int i = l; i <= r; i++)
if (depth[euler[i]] < depth[euler[best]]) best = i;
return euler[best]; // 用 RMQ(ST 表)可优化到 O(1)
}
朴素找最小值是 O(n),配合 ST 表(区间最小值)即可 O(1) 查询 LCA。
五者关系一览
一次 DFS 遍历
│
┌──────────┼──────────┬──────────────┐
│ │ │ │
子树大小 深度 DFS 序 欧拉序
sz[u] dep[u] tin/tout 2n-1 长
│ │ │
├─ 求重心 ├─ 子树转区间 ├─ LCA(RMQ)
├─ 求直径 ├─ 祖先判断 ├─ 树上路径
└─ 树形 DP └─ 配合树状数组/线段树
一次 DFS 就能同时算出所有这些信息,关键在于遍历时顺手维护:
void dfs(int u, int fa) {
sz[u] = 1;
depth[u] = depth[fa] + 1;
tin[u] = ++timer;
euler.push_back(u);
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
euler.push_back(u);
}
tout[u] = timer;
}
常见错误
- 重心统计漏掉父节点侧:忘记
n - sz[u],结果永远偏向根。 - 直径用两遍 DFS 却带负边权:会得到错误答案,必须改用树形 DP。
- DFS 序区间用错:
tout[u]是子树最后一个节点的编号,区间是[tin[u], tout[u]]闭区间。 - 递归爆栈:n 达到 10^5 以上时链状树会爆栈,需改迭代或加栈空间。
- 欧拉序长度算错:n 个节点、n-1 条边,欧拉序长度为
2n - 1。
小结
四个工具都由一次 DFS 得到:重心靠 sz 的最大分支,直径靠最远点两遍 DFS 或树形 DP,DFS 序把子树变成连续区间(配合线段树解决子树操作),欧拉序配合 RMQ 求 LCA。掌握它们,树上问题就解决了一大半。