我的算法书 - 树的直径

一句话算法

从任意点走到最远点，再从这个最远点走到另一个最远点，两点之间的距离就是树的直径。

问题模型

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

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

“树的直径”

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

核心直觉

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

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

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

算法步骤

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

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

算法证明

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

设树上一条直径为 a -> b。考虑 s 到 u 的路径与直径 a -> b 的交点区域。

如果 u 不是直径端点，那么从交点继续走向 u 的那条分支，不会比走向直径某一端更短；否则 u 就不可能是离 s 最远的点。

于是可以把直径的一端替换成 u，得到一条长度不小于原直径的路径。因此 u 至少是某条最长路径的端点。

第二次从 u 出发找最远点 v。因为 u 是某条直径端点，从 u 能到达的最远距离正好就是直径长度，所以 u -> v 是直径。

复杂度分析

设点数为 $n$ 。

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

代码实现

输入格式采用常见模板：

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
70
71
72
73
74

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

struct TreeDiameter {
    using ll = long long;

    int n = 0;
    vector<vector<pair<int, ll>>> graph;

    TreeDiameter(int n = 0) {
        init(n);
    }

    void init(int node_count) {
        n = node_count;
        graph.assign(n + 1, {});
    }

    void add_edge(int u, int v, ll w) {
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    pair<int, ll> farthest_from(int start) const {
        vector<ll> dist(n + 1, -1);
        stack<int> st;
        st.push(start);
        dist[start] = 0;

        int farthest = start;
        while (!st.empty()) {
            int u = st.top();
            st.pop();

            if (dist[u] > dist[farthest]) {
                farthest = u;
            }

            for (auto [v, w] : graph[u]) {
                if (dist[v] != -1) continue;
                dist[v] = dist[u] + w;
                st.push(v);
            }
        }

        return {farthest, dist[farthest]};
    }

    tuple<int, int, ll> solve() const {
        auto [left, _] = farthest_from(1);
        auto [right, diameter] = farthest_from(left);
        return {left, right, diameter};
    }
};

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

    int n;
    cin >> n;

    TreeDiameter solver(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        solver.add_edge(u, v, w);
    }

    auto [u, v, diameter] = solver.solve();
    cout << diameter << '\n';
    return 0;
}

测试用例

输入：

输出：

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

应用分类详解

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

一、直接求最长路径

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

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

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

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

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

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

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

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

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

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

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

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

经典例题

1. 树上最长路模板题

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

2. 树的中心类题目

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

3. luogu-P3304

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

参考

本书树的中心章节：graph/center_of_tree/index.md