我的算法书 - 树的直径

一句话算法

两次搜索：先找到一个最远端点，再从它找到另一个最远端点。
树形 DP：枚举路径的最高点，把两条最长向下链拼起来。

问题模型

给定一棵树，边可以带非负权。

两点距离：树上唯一简单路径的边权和。
树的直径：任意两点距离的最大值。
目标：求直径长度，有时还需要求直径的两个端点。

树的直径

树上最长简单路径叫做树的直径。

边权范围

本文只讨论非负边权。长度为 $0$ 的链表示停在当前节点，因此单节点树的直径为 $0$ 。

方法一：两次最远点搜索

核心直觉

树没有环，所以任意两点之间只有一条路。

如果从任意点 s 出发，找到最远点 u，这个 u 一定已经被推到了树的某个“边界”。直径一定从一个边界走到另一个边界，所以再从 u 出发找最远点 v，路径 u -> v 就是最长路径。

可以把第一次搜索理解成“找到一端”，第二次搜索理解成“从这一端拉到最远”。

算法步骤

从任意点开始搜索，通常选 1。
计算所有点到 1 的距离，找到最远点 u。
从 u 再搜索一次，计算所有点到 u 的距离。
找到最远点 v。
dist(u, v) 就是树的直径长度。

搜索可以使用 DFS 或 BFS。因为树上路径唯一，即使边有权，也不需要 Dijkstra；沿树遍历时累加边权即可。

正确性证明

核心结论：从任意点 $s$ 出发找到的最远点 $u$ ，一定是某条直径的端点。

先固定一条直径 $a \to b$ ，记它的长度为

D = dist(a,b)

反设 $u$ 不是任何直径的端点。

直觉模型：如果把直径的一端换成 $u$ ，路径长度不会变短；这样最终就能得到一条以 $u$ 为端点的直径。

情况一： $s \to u$ 与直径没有公共点

两条路径之间有一条唯一的连接路径。设它在 $s \to u$ 上的端点为 $x$ ，在直径 $a \to b$ 上的端点为 $c$ 。从 $s$ 到 $a$ 、 $b$ 都要先经过 $x$ 和 $c$ 。

搜索路径与直径不相交时，通过连接路径 x 到 c 比较分支并用 u 替换直径端点

因为 $u$ 是 $s$ 的最远点， $dist(s,u) \geqslant dist(s,a)$ 。展开两条路径并消去公共的 $s \to x$ 段，得到

dist(x,u) \geqslant dist(x,c)+dist(c,a)

于是

\begin{aligned} dist(u,b) &= dist(u,x)+dist(x,c)+dist(c,b) \\ &\geqslant dist(c,a)+dist(c,b)+2dist(x,c) \\ &\geqslant dist(a,b)=D \end{aligned}

但 $D$ 已经是树上任意两点距离的最大值，所以只能有 $dist(u,b)=D$ 。这说明 $u \to b$ 也是一条直径，与反设矛盾。

因此， $s \to u$ 必定与直径相交。

情况二： $s \to u$ 与直径相交

取公共部分中离 $u$ 最近的点 $x$ 。树没有环，公共部分是一段连续路径；将直径两端重新命名，使得从 $s$ 到 $a$ 的路径经过 $x$ ， $b$ 是另一端。

搜索路径与直径在 x 相交时，比较 x 到 u 和 x 到 a，并用 u 替换直径端点

$s \to u$ 和 $s \to a$ 共享 $s \to x$ 段。由于 $u$ 是 $s$ 的最远点，消去这段公共路径可得

dist(x,u) \geqslant dist(x,a)

而 $u \to b$ 的路径经过 $x$ ，所以

\begin{aligned} dist(u,b) &= dist(u,x)+dist(x,b) \\ &\geqslant dist(x,a)+dist(x,b) \\ &= dist(a,b)=D \end{aligned}

同样因为 $D$ 是最大距离，只能取等号。于是 $u \to b$ 是一条直径， $u$ 是直径端点，再次与反设矛盾。

综上，从任意点 $s$ 出发找到的最远点 $u$ ，一定是某条直径的端点。

第二次从 $u$ 出发找最远点 $v$ 。刚才已经证明 $u$ 是某条直径的端点，因此从 $u$ 出发至少能走到距离 $D$ 的点；又因为 $D$ 是全树最大距离，不可能走得更远。所以 $dist(u,v)=D$ ， $u \to v$ 就是树的直径。

复杂度分析

设点数为 $n$ 。

时间复杂度： $O(n)$ 。两次遍历整棵树。
空间复杂度： $O(n)$ 。邻接表和距离数组。

代码模板

farthest 做一次最远点搜索；solve 连续调用两次后，直径长度存在 ans，端点是 a、b。

队列写法

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

        #include <queue>
#include <vector>

const int maxn = 1e6 + 5;
using ll = long long;
using Edge = struct { int to; ll w; };
using Graph = std::vector<Edge>;
Graph tree[maxn];  // 全局邻接表数组：直接向 tree[u] 加带权边

// 如何使用：
// 1. 读入带权边：tree[u].push_back({v, w}); tree[v].push_back({u, w});
// 2. TreeDiameter td(n);
// 3. td.solve(); cout << td.ans;  // 直径长度在 td.ans，端点是 td.a、td.b

// 求树的直径：任意点出发找最远点 u，再从 u 找最远点 v，u -> v 就是直径。
struct TreeDiameter {
    int n;
    int a, b;            // 直径的两个端点
    ll ans;              // 直径长度
    std::vector<ll> dis; // 到当前起点的距离

    explicit TreeDiameter(int n) : n(n), a(0), b(0), ans(0), dis(n + 1) {}

    // 从 s 出发找最远点，返回最远点的编号
    int farthest(int s) {
        dis.assign(n + 1, -1);
        std::queue<int> q;
        q.push(s);
        dis[s] = 0;
        int far = s;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (dis[u] > dis[far]) far = u;
            for (Edge e : tree[u]) {
                int v = e.to;
                ll w = e.w;
                if (dis[v] != -1) continue;
                dis[v] = dis[u] + w;
                q.push(v);
            }
        }
        return far;
    }

    // 两次最远点搜索：端点存入 a、b，长度存入 ans
    void solve() {
        a = farthest(1);
        b = farthest(a);
        ans = dis[b];
    }
};

DFS 写法

如果题目还需要输出直径上的节点，可以使用 DFS 版本。第二次 DFS 会记录 parent，从右端点一路跳父节点即可还原整条直径路径。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

        #include <algorithm>
#include <vector>

const int maxn = 1e6 + 5;
using ll = long long;
using Edge = struct { int to; ll w; };
using Graph = std::vector<Edge>;
Graph tree[maxn];  // 全局邻接表数组：直接向 tree[u] 加带权边

// 如何使用：
// 1. 读入带权边：tree[u].push_back({v, w}); tree[v].push_back({u, w});
// 2. TreeDiameterDFS td(n);
// 3. td.solve();
//    直径长度在 td.ans，端点是 td.a、td.b，路径是 td.path。

// 两次 DFS 最远点搜索求树的直径，并记录直径路径。
struct TreeDiameterDFS {
    int n;
    int a, b;                // 直径的两个端点
    ll ans;                  // 直径长度
    std::vector<ll> dis;     // dis[u] = 当前 DFS 起点到 u 的距离
    std::vector<int> parent; // parent[u] = 当前 DFS 中 u 的父节点，用于还原路径
    std::vector<int> path;   // 从 a 到 b 的直径路径

    explicit TreeDiameterDFS(int n)
        : n(n), a(0), b(0), ans(0), dis(n + 1), parent(n + 1) {}

    void dfs(int u, int fa, ll d) {
        dis[u] = d;
        parent[u] = fa;
        for (Edge e : tree[u]) {
            int v = e.to;
            if (v == fa) continue;
            dfs(v, u, d + e.w);
        }
    }

    int farthest(int s) {
        dfs(s, 0, 0);
        int far = s;
        for (int u = 1; u <= n; u++) {
            if (dis[u] > dis[far]) far = u;
        }
        return far;
    }

    void build_path() {
        path.clear();
        for (int u = b; u != 0; u = parent[u]) {
            path.push_back(u);
            if (u == a) break;
        }
        std::reverse(path.begin(), path.end());
    }

    // 两次最远点搜索：端点存入 a、b，长度存入 ans，路径存入 path。
    void solve() {
        a = farthest(1);
        b = farthest(a);
        ans = dis[b];
        build_path();
    }
};

方法二：树形 DP

核心直觉

把树以 1 为根。节点越靠近根，深度越小。一条简单路径上深度最小的节点是唯一的，称为这条路径的最高点。

如果一条路径的最高点是 $u$ ，那么它有两种形态：

从 $u$ 沿一个儿子方向向下走，此时另一条链的长度视为 $0$ ；
从一个儿子子树走到 $u$ ，再进入另一个儿子子树。

因此，只要知道每个儿子方向提供的最长链，就可以在 $u$ 处把其中两条拼成路径。

状态定义

定义 $f[u]$ 为：dfs(u) 结束后，从 $u$ 出发、只向它的子树走，能够得到的最长链长度。

对于 $u$ 的儿子 $v$ ，设边权为 $w(u,v)$ ，从 $u$ 进入 $v$ 子树的候选链长为

c_v=f[v]+w(u,v)

叶子没有儿子，所以 $f[u]=0$ 。对于非叶子，最终有

f[u]=\max_v c_v

从二重枚举到一次扫描

若 $u$ 有 $k$ 个儿子，把长度为 $0$ 的空链记作 $c_0$ 。朴素做法会枚举两条不同的链：

\max_{0\leqslant i<j\leqslant k}(c_i+c_j)

这样在节点 $u$ 需要 $O(\deg^2(u))$ 时间。

现在按顺序扫描儿子。处理第 $j$ 条链时，只需要知道前面链长的最大值

mx=\max_{0\leqslant i<j}c_i

代码直接复用 f[u] 保存这个 mx。处理当前儿子 $v$ 时，先拼接两条链：

ans=\max\bigl(ans,\ f[u]+f[v]+w(u,v)\bigr)

再把当前链并入已经处理的链：

f[u]=\max\bigl(f[u],\ f[v]+w(u,v)\bigr)

当还没有处理任何儿子时，f[u]=0。这个 $0$ 表示路径可以从 $u$ 开始，因此同一套转移也覆盖只使用一条向下链的路径。

更新顺序不能交换

必须先更新 ans，再更新 f[u]。如果顺序反过来，f[u] 可能已经包含当前儿子 $v$ ，计算答案时就会把同一个儿子方向使用两次，得到的不是合法简单路径。

算法步骤

把树以 1 为根，执行后序 DFS。
处理 $u$ 时，先递归算出每个儿子 $v$ 的 $f[v]$ 。
用 f[u] + f[v] + w(u,v) 更新全局答案。
用 f[v] + w(u,v) 更新 f[u]。
DFS 结束后，全局答案就是直径长度。

正确性证明

证明只需要抓住两个不变量，再说明它们覆盖了所有路径。

1. 子树状态

叶子的 $f[u]=0$ 。对于非叶子 $u$ ，任意向下链都必须先进入某个儿子 $v$ ，该方向的最长链为 $f[v]+w(u,v)$ 。扫描完所有儿子后，f[u] 取到了这些链的最大值，所以 dfs(u) 结束时状态定义成立。

2. 儿子扫描

处理当前儿子 $v$ 之前，f[u] 始终是已处理儿子提供的最长链。因此

f[u]+f[v]+w(u,v)

就是“此前最佳方向”和“当前方向”在 $u$ 处拼成的最长路径。更新 ans 后，再把当前链加入 f[u]，这个不变量继续成立。扫描结束时，每个当前方向都已经和此前的最佳方向配对。

最后考虑整棵树中的任意简单路径。它有唯一的最高点 $u$ ：

若一个端点就是 $u$ ，路径对应一条向下链和长度为 $0$ 的空链；
否则，两个端点位于 $u$ 的不同儿子子树中，路径由两个方向的向下链拼成。

DFS 处理了每个节点，也就枚举了每个可能的最高点。算法得到的候选都是合法路径，并覆盖了每个最高点处的最长路径，因此全局最大值 ans 就是树的直径。

另一种等价写法

也可以先找出所有儿子链中的最长值 best1 和次长值 best2。扫描每条链 len 时，核心更新为：

cpp

        1
2
3
4
5
6

        if (len > best1) {
    best2 = best1;
    best1 = len;
} else if (len > best2) {
    best2 = len;
}

扫描结束后，f[u]=best1，经过 $u$ 的最长路径是 best1 + best2。这与模板中的在线写法完全等价：模板里的 f[u] 就是“已处理儿子中的 best1”，当前链是本次与它配对的另一条链。

复杂度分析

时间复杂度： $O(n)$ 。每个儿子只合并一次，整棵树共处理 $n-1$ 条父子边。
空间复杂度： $O(n)$ 。邻接表、 $f$ 数组和递归栈都可能达到线性规模。

代码模板

solve 从节点 1 开始后序遍历，直径长度保存在 ans 中。这个模板只统计长度，不记录直径端点。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

        #include <algorithm>
#include <vector>

const int maxn = 1e6 + 5;
using ll = long long;
using Edge = struct { int to; ll w; };
using Graph = std::vector<Edge>;
Graph tree[maxn];  // 全局邻接表数组：直接向 tree[u] 加带权边

// 如何使用：
// 1. 读入带权边：tree[u].push_back({v, w}); tree[v].push_back({u, w});
// 2. TreeDiameterDP td(n);
// 3. td.solve(); cout << td.ans;  // 直径长度在 td.ans

// 树上 DP 求直径：对每个点统计"往下走的最长链"。
// 扫描 u 的儿子时，f[u] 表示已处理儿子提供的最长链；当前儿子 v
// 提供 f[v] + w。先用这两条链更新直径，再把当前链并入 f[u]。
struct TreeDiameterDP {
    int n;
    ll ans;              // 直径长度
    std::vector<ll> f;   // f[u] = 从 u 出发往下走的最长链长度

    explicit TreeDiameterDP(int n) : n(n), ans(0), f(n + 1) {}

    void solve() { dfs(1, 0); }

    // 后序遍历：处理儿子 v 时，f[u] 还是"已处理儿子的最长链"，
    // 先 ans = max(ans, f[u] + f[v] + w) 用两条链在 u 拼接，
    // 再 f[u] = max(f[u], f[v] + w) 把当前儿子的链并入 f[u]。
    void dfs(int u, int parent) {
        for (Edge e : tree[u]) {
            int v = e.to;
            ll w = e.w;
            if (v == parent) continue;
            dfs(v, u);

            ans = std::max(ans, f[u] + f[v] + w); // 过 u 的两条链拼接（f[u] 为 0 时就是单链）
            f[u] = std::max(f[u], f[v] + w);      // 更新过 u 的最长向下链
        }
    }
};

递归深度

当树退化成长链时，递归深度会达到 $O(n)$ 。数据规模较大时，应改成迭代后序遍历，或者使用方法一的队列实现。

两种方法怎么选

对比项	两次最远点搜索	树形 DP
遍历方式	两次完整遍历	一次后序遍历
直接得到	直径长度和两个端点	直径长度
深树风险	队列实现不依赖递归栈	递归实现可能栈溢出
适用场景	普通树直径问题	已在进行树形 DP，需顺便统计最长路径

两种方法的时间、空间复杂度都是 $O(n)$ 。如果题目需要直径端点，优先使用两次最远点搜索；如果只需要长度，并且题目本身已有树形 DP，第二种方法更自然。

模板二选一

两份模板共用了 tree、Edge 等全局名称，应根据题目需要选择其中一份，不要同时复制到同一份源码中。

完整代码实现

以下两份程序使用相同的输入格式：

n
u1 v1 w1
u2 v2 w2
...
u(n-1) v(n-1) w(n-1)

输出直径长度。

两次最远点搜索

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;
using ll = long long;
using Edge = struct { int to; ll w; };
using Graph = vector<Edge>;
Graph tree[maxn];  // 全局邻接表数组：直接向 tree[u] 加带权边

// 求树的直径：任意点出发找最远点 u，再从 u 找最远点 v，u -> v 就是直径。
struct TreeDiameter {
    int n;
    int a, b;            // 直径的两个端点
    ll ans;              // 直径长度
    vector<ll> dis;      // 到当前起点的距离

    explicit TreeDiameter(int n) : n(n), a(0), b(0), ans(0), dis(n + 1) {}

    // 从 s 出发找最远点，返回最远点的编号
    int farthest(int s) {
        dis.assign(n + 1, -1);
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        int far = s;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (dis[u] > dis[far]) far = u;
            for (Edge e : tree[u]) {
                int v = e.to;
                ll w = e.w;
                if (dis[v] != -1) continue;
                dis[v] = dis[u] + w;
                q.push(v);
            }
        }
        return far;
    }

    // 两次最远点搜索：端点存入 a、b，长度存入 ans
    void solve() {
        a = farthest(1);
        b = farthest(a);
        ans = dis[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i < n; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }

    TreeDiameter td(n);
    td.solve();
    cout << td.ans << '\n';
    return 0;
}

树形 DP

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

        #include <algorithm>
#include <iostream>
#include <vector>

const int maxn = 1e6 + 5;
using ll = long long;
using Edge = struct { int to; ll w; };
using Graph = std::vector<Edge>;
Graph tree[maxn];

// 树上 DP 求直径：扫描 u 的儿子时，用 f[u] 维护此前最长链，
// 再把当前儿子的链与它拼起来更新直径。
struct TreeDiameterDP {
    int n;
    ll ans;
    std::vector<ll> f; // f[u] = 从 u 出发往下走的最长链长度

    explicit TreeDiameterDP(int n) : n(n), ans(0), f(n + 1) {}

    void solve() { dfs(1, 0); }

    void dfs(int u, int parent) {
        for (Edge e : tree[u]) {
            int v = e.to;
            ll w = e.w;
            if (v == parent) continue;
            dfs(v, u);

            // 必须先更新答案，确保 f[u] 还不包含当前儿子 v。
            ans = std::max(ans, f[u] + f[v] + w);
            f[u] = std::max(f[u], f[v] + w);
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    for (int i = 1; i < n; ++i) {
        int u, v;
        ll w;
        std::cin >> u >> v >> w;
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }

    TreeDiameterDP td(n);
    td.solve();
    std::cout << td.ans << '\n';
    return 0;
}

测试用例

输入：

输出：

解释：最长路径是 5 -> 3 -> 2 -> 4 -> 6，长度为 1+2+4+2=9。

树形 DP 状态演算

以 1 为根。递归处理完节点 3、4 后，已有 $f[3]=1$ 、 $f[4]=2$ 。下面观察节点 2 如何依次合并两个儿子：

当前儿子 $v$	当前链 $f[v]+w(2,v)$	合并前 $f[2]$	候选路径	合并后 $f[2]$
`3`	$1+2=3$	$0$	$0+3=3$	$3$
`4`	$2+4=6$	$3$	$3+6=9$	$6$

处理儿子 4 时，f[2]=3 仍表示此前经过儿子 3 的最长链；它与当前长度为 $6$ 的链拼接，得到直径长度 $9$ 。随后才把 f[2] 更新为 $6$ 。

应用分类详解

树的直径本质上是在树中寻找“最远的两个边界点”。只要题目出现树上最远距离、最长路径、中心点，通常都要先想到直径。

一、直接求最长路径

典型模式： 给一棵树，问任意两点之间最远距离。

识别信号： 出现“树上最长路”“最远两点”“最大距离”。

核心建模： 边权就是路径代价，两次最远点搜索直接求直径。

应用场景	经典题目	核心思路
树直径模板	树上最长路模板题	两次 DFS/BFS 找最长路
无权树最长路	树上基础题	每条边权视为 `1`

二、树的中心与最小最大距离

典型模式： 在树上选一个点，使它到所有点的最大距离尽量小。

识别信号： 出现“选址”“到最远点距离最小”“中心”。

核心建模： 树的最优中心一定在直径中点附近。

三、树上路径覆盖与删边问题

典型模式： 先找出最长路径，再围绕这条路径处理分支。

识别信号： 出现“所有点到某条主干的距离”“保留一条链”“走遍整棵树”。

核心建模： 直径提供树中最极端的主路径，其余部分是挂在直径上的子树。

经典例题

1. 树上最长路模板题

树直径模板题。适合练习两次 DFS/BFS 的基本写法。

2. 树的中心类题目

重点是把“最小化到最远点的距离”转成直径中点模型。

3. luogu-P3304

SDOI2013 直径。除了求直径，还要分析哪些边一定在所有直径上，适合进一步理解直径结构。

参考

本书树的中心章节：tree-algo/center_of_tree/index.md

一句话算法

问题模型

方法一：两次最远点搜索

核心直觉

算法步骤

正确性证明

情况一：s→us \to us→u 与直径没有公共点

情况二：s→us \to us→u 与直径相交

复杂度分析

代码模板

队列写法

DFS 写法

方法二：树形 DP

核心直觉

状态定义

从二重枚举到一次扫描

算法步骤

正确性证明

另一种等价写法

复杂度分析

代码模板

两种方法怎么选

完整代码实现

两次最远点搜索

树形 DP

测试用例

树形 DP 状态演算

应用分类详解

一、直接求最长路径

二、树的中心与最小最大距离

三、树上路径覆盖与删边问题

经典例题

1. 树上最长路模板题

2. 树的中心类题目

3. luogu-P3304

参考

情况一： $s \to u$ 与直径没有公共点

情况二： $s \to u$ 与直径相交