困难C++4 分钟1,461 字

树的重心、直径、DFS 序与欧拉序

树是竞赛中最常见的结构,而"重心、直径、DFS 序、欧拉序"是处理树上问题的四把钥匙。2025 年 CSP-S 真题「社团招新」就考了 DFS 序的应用,属于当前命题的热点方向。

一、树的重心

定义​​:删除某个节点后,树上最大的连通块节点数最小​​,这个节点叫重心。

一棵树的重心最多有两个(且相邻)。

求法

任选根做一次 DFS,求出每个节点的子树大小 sz[u]。对节点 u,删掉它之后,最大的连通块是:

max( 每个儿子的 sz[son],  n - sz[u] )

其中 n - sz[u] 是"父节点那一侧"的节点数。

cpp
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(只能处理非负边权)

  1. 任取一点 p,DFS 找到距离 p 最远的点 a
  2. 从 a 再 DFS,找到距离 a 最远的点 b
  3. a 到 b 的路径就是直径
cpp
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(支持负边权)

cpp
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 的序列。

cpp
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) 内完成子树操作。

cpp
// 例子:树状数组维护子树的某些信息
// 建树时按 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]。

cpp
bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

四、欧拉序

定义​​:DFS 经过节点时记录,​每次进入和离开都记录一次​​,得到长度为 2n-1 的序列。

cpp
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​​。

cpp
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 就能同时算出所有这些信息​​,关键在于遍历时顺手维护:

cpp
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。掌握它们,树上问题就解决了一大半。

同类知识点