我的算法书 -

树的直径定义

给定一棵带权(边)树

距离: 两个点路径上的边权和
树的直径: 最大距离

两次dfs法求直径

从任意一点 $u$ 出发，找到距离 $u$ 最远的点 $v$
从点 $v$ 出发，找到距离 $v$ 最远的点 $w$ ，则 $v$ 到 $w$ 的路径就是树的直径

定理 1

从任意一点 $u$ 出发，找到距离 $u$ 最远的点 $v$ ，则 $v$ 一定是直径的某个端点

证明定理 1

我们使用反证法来证明。

假设：定理不成立。即，从任意点 $u$ 出发找到的最远点 $v$ ，不是任何一条直径的端点。

那么,我们可以进行如下推理：

设树上的一条直径为路径 $(a, b)$ ，其长度为 $L_{ab}$ 。根据我们的假设，有 $v \neq a$ 且 $v \neq b$ 。
根据 $v$ 的定义（距离 $u$ 最远的点），对于树上任意一点 $x$ ，都有 $dist(u, v) \geqslant dist(u, x)$ 。特别地，我们有 $dist(u, v) \geqslant dist(u, a)$ 。

下点分情况讨论:

情况1: $u$ 在直径 $(a,b)$ 上

Open in Excalidraw

显然可以得到:

$x_1 + x_3 > x_1 + x_2$
于是得到 $L_{au} +x1 + x3 >L_{au} +x_1 + x_2$
于是得到了一条比直径 $L_{ab}$ 更长的路径, 矛盾.

情况2: $u$ 在不直径 $(a,b)$ 上, 且路径 $(u,v)$ 与直径 $(a,b)$ 不相交

Open in Excalidraw

因为树上的任意两个点都存在唯一的路径, $u$ 可以到达直径 $(a,b)$ 上的任意一点, 设 $u$ 到 $a$ 的距离为 $L_{ut}$ ,那么 $t$ 点就是最近的点
显然可以得到 $L_{ut} + L_{tb} < L_{ut} + L_{uv}$ (因为 $v$ 是 $u$ 的最远点)
于是得到 $L_{uv} > L_{ub}$
但是根据 $v$ 的定义, $L_{av} > L_{ab}$
矛盾

情况3: $u$ 在不直径 $(a,b)$ 上, 且路径 $(u,v)$ 与直径 $(a,b)$ 相交

Open in Excalidraw

同样的思路:

$L_{uv} > L_{ub}$
$L_{t_1 v} > L_{t_1 b}$
$L_{av} > L_{ab}$
矛盾

因此，假设不成立，原定理得证。

证明

算法:

第一次 DFS 从任意点 $u$ 找到最远点 $v$ ，根据引理， $v$ 是直径端点
第二次 DFS 从 $v$ 找到最远点 $w$ ，则 $(v,w)$ 就是直径

代码实现

cpp

copy

        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

        int max_dist, farthest_node;

void dfs_find_farthest(int u, int fa, int dist) {
    if (dist > max_dist) {
        max_dist = dist;
        farthest_node = u;
    }
    
    for (int i = e.h[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        dfs_find_farthest(v, u, dist + e[i].w);
    }
}

int tree_diameter() {
    // 第一次DFS：从任意点(如1)找到最远点
    max_dist = 0;
    dfs_find_farthest(1, 0, 0);
    int v = farthest_node;
    
    // 第二次DFS：从v找到最远点，距离即为直径
    max_dist = 0;
    dfs_find_farthest(v, 0, 0);
    return max_dist;
}

时间复杂度: $O(n)$ ，两次 DFS 遍历整棵树 空间复杂度: $O(n)$ ，递归栈空间:

DP求树的直径

我们认为(假定)树的根为 $1$ ,

$tree(i)$ 表示以点 $i$ 为根的子树.
$pathLca(i)$ 表示路径上的两个端点的lca为点 $i$ 的路径的集合

\text{所有路径的集合} = \bigcup_{i=1}^n pathLca(i)

根据公式

A = B \cup C \to \max(A) = \max(\ \max(B) , \max(C)\ )

那么答案就是

max\_ans = \max_{i=1}^n ( \max( pathLca(i) ) )

于是问题转换成求 $P(i) = \max ( pathLca(i) )$ ,易想到

$P(i)$ 表示经过点 $i$ 的最长链,且 $i$ 是链的 $lca$
$D(i)$ 表示点 $i$ 到叶结点的最长链
$x_i$ 表示点 $i$ 的孩子
$e(i,x_i)$ 表示边 $(i , x_i)$ 的长度

D(i) = \max \{ D(x_i) + e(i,x_i) \}

P(i) = \max\{ D(x_i)+ e(i,x_i) + D(y_i) + e(i,y_i) \} , x_i < y_i

设 $Dt(i,x_i) = D(x_i) + e(i,x_i)$

那么这个问题就变成的集合最大二值和问题

Open in Excalidraw

于是我们得到代码如下:

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

        int ans;

template<typename T>
void upd(T& v,T t) { if( v < t) v = t; } 

void dfs_dp(int u,int fa) {
    
    int pathlca = 0;
    for(int i = e.h[u];i != -1; i = e[i].next)
    {
        int v = e[i].v;
        if( v == fa) continue;
        dfs_dp(v, u);
        int dt = d[v] + e[i].w; //得到 u到达 v 子树上的最远点
        upd(pathlca,d[u] + dt); // 得到 分类 dt 的结尾的最值,更新 pathlca
        upd(d[u],dt); // 更新d[u]
    }
    upd(ans,pathlca);
}

树的所有直径拥有相同的中点

反证法:

假设有两条不相交的直径

因为树上任意两点都有一条唯一的路径

那么假设连接两个中点的长度为len, 直径长度为max_d

那么两条直径的两端距离为max_d + len > max_d

那么直径长度不是len

矛盾

所以两条直径必须经过一个点

定理: 树的所有直径都经过相同的中点（或中点所在的边）。

证明

定义:

路径的中点：将路径分成两个相等长度的点（或边）
如果直径长度为偶数，中点是一个确定的点
如果直径长度为奇数，中点是一条确定的边

反证法证明:

假设存在两条直径 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，它们的中点不同。

设：

$M_1$ 为直径 $(x_1,y_1)$ 的中点
$M_2$ 为直径 $(x_2,y_2)$ 的中点
直径长度为 $L$

情况1：中点都是点（直径长度为偶数）

由于 $M_1 \neq M_2$ ，考虑路径 $M_1 \to M_2$ 。在树中，两点间只有唯一路径。

考虑以下四个距离：

$dist(M_1, x_1) = dist(M_1, y_1) = L/2$ （中点定义）
$dist(M_2, x_2) = dist(M_2, y_2) = L/2$ （中点定义）

由于 $M_1 \neq M_2$ ，不失一般性，设 $M_2$ 在 $M_1$ 到 $x_1$ 的路径上。

则：

$dist(M_2, x_1) < L/2$
$dist(M_2, y_1) > L/2$

但 $dist(M_2, x_2) = L/2$ ，且 $(x_2,y_2)$ 是直径，所以：

L = dist(x_2, y_2) \leq dist(x_2, M_2) + dist(M_2, y_2) = L/2 + dist(M_2, y_2)

这意味着 $dist(M_2, y_2) \geq L/2$ ，结合 $dist(M_2, y_1) > L/2$ ，可以得到：

dist(x_2, y_1) = dist(x_2, M_2) + dist(M_2, y_1) > L/2 + L/2 = L

这与 $L$ 是最大距离（直径长度）矛盾！

情况2：中点都是边（直径长度为奇数）

设 $M_1 = (a_1,b_1)$ ， $M_2 = (a_2,b_2)$ 是两条边。

类似的论证可以证明，如果中点边不同，也能构造出比直径更长的路径，产生矛盾。

结论: 因此，树的所有直径必须有相同的中点。

推论与应用

树的中心: 所有直径的中点（或中点边）的集合称为树的中心
中心性质:
- 如果直径长度为偶数，中心是单个点
- 如果直径长度为奇数，中心是两个相邻的点（一条边）
应用: 这个性质在很多树算法中有重要应用，如：
- 找树的最小高度根节点
- 网络布局优化
- 树的重心相关问题

代码验证

cpp

copy

        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

        // 验证所有直径是否经过相同中点
vector<int> diameter_path;  // 存储直径路径
vector<int> center_points;  // 存储中心点

void find_diameter_path(int u, int fa, int target, vector<int>& path) {
    path.push_back(u);
    if (u == target) return;
    
    for (int i = e.h[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        find_diameter_path(v, u, target, path);
        if (path.back() == target) return;
    }
    path.pop_back();
}

void find_center() {
    int v = find_farthest(1, 0);
    int w = find_farthest(v, 0);
    
    vector<int> path;
    find_diameter_path(v, 0, w, path);
    
    int diameter_length = path.size() - 1;
    if (diameter_length % 2 == 0) {
        // 中心是单个点
        center_points.push_back(path[diameter_length / 2]);
    } else {
        // 中心是两个点
        center_points.push_back(path[diameter_length / 2]);
        center_points.push_back(path[diameter_length / 2 + 1]);
    }
}

树的直径的重合部分

重要性质: 树的所有直径有且只有一段重合的部分，这段重合可能是：

一个点（当直径长度为偶数时）
一条边（当直径长度为奇数时）

证明

基于前面证明的"所有直径拥有相同的中点"性质：

所有直径都经过相同的中点区域
- 如果直径长度为偶数，所有直径都经过同一个中心点
- 如果直径长度为奇数，所有直径都经过同一条中心边
重合部分的唯一性
- 设树的中心区域为 $C$ （点或边）
- 任意直径都必须完整包含 $C$
- 在 $C$ 之外，不同直径可能分叉到不同的端点
重合部分的最大性
- 重合部分不能更长，否则会有直径不包含某个端点
- 重合部分不能更短，否则会有直径不经过中心

直观理解

想象一棵树的形状：

        A       B       C
         \     / \     /
          \   /   \   /
            D       E
           / \     / \
          F   G   H   I
         / \     / \ / \
        J   K   L  M N  O

如果直径长度为偶数，所有直径都经过中心点 D
如果直径长度为奇数，所有直径都经过中心边 (D,E)

应用：NOI2013 快餐店

这是一个经典的应用题，需要在树上设置一个快餐店，使得所有点到快餐店的最大距离最小。

解题思路：

找到所有直径的公共重合部分
将快餐店设在重合部分的中点
这样可以最大化地减少最远距离

代码实现：

cpp

copy

        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

        // 找到所有直径的重合部分
vector<int> find_common_path() {
    // 找到一条直径的端点
    int v = find_farthest(1, 0);
    int w = find_farthest(v, 0);
    
    // 找到所有直径端点
    vector<int> diameter_ends = find_all_diameter_ends(v, w);
    
    // 找到重合部分的起点和终点
    int common_start = n, common_end = 1;
    
    for (int end : diameter_ends) {
        vector<int> path1, path2;
        find_path(v, end, path1);
        find_path(w, end, path2);
        
        // 找到两条路径的公共部分
        int lca_node = lca(v, end);
        // 更新重合部分的边界
        update_common_boundary(path1, path2, common_start, common_end);
    }
    
    return get_common_path(common_start, common_end);
}

// 快店店问题的核心代码
double solve_restaurant() {
    vector<int> common_path = find_common_path();
    
    if (common_path.size() == 1) {
        // 重合部分是一个点
        return max_distance_from_point(common_path[0]);
    } else {
        // 重合部分是一条路径
        return max_distance_from_path(common_path);
    }
}

总结

这个性质告诉我们：

树的直径虽然可能有很多条，但它们有很强的规律性
所有直径都会在树的"中心区域"重合
这个性质是解决很多树问题的基础，特别是涉及最优化的问题
在实际应用中，可以利用这个性质来简化问题的复杂度

直径必过边

对应题目: luogu P3304 SDOI2013 直径

两次 dfs 法

DP 法

参考

树的直径题目单 https://www.luogu.com.cn/training/505787#problems

NOI2013有个叫快餐店

最终模板代码:

cpp

copy

        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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305

        /**
 * 树直径算法完整版本
 * 包含：DFS、BFS、Dijkstra三种实现
 * 适用于不同边权情况
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200005;
const long long INF = 1e18;

// 边结构（支持任意权重）
struct Edge {
    int to, next;
    long long w;
    Edge(int t = 0, int n = 0, long long w = 0) : to(t), next(n), w(w) {}
} e[maxn << 1];

int head[maxn], cnt;
int n;

void add_edge(int u, int v, long long w = 1) {
    e[++cnt] = Edge(v, head[u], w);
    head[u] = cnt;
    e[++cnt] = Edge(u, head[v], w);
    head[v] = cnt;
}

template<int N = maxn>
struct TreeDiameterAdvanced {
    long long dis[N];        // 距离数组
    int parent[N];          // 父节点数组
    bool visited[N];        // 访问标记
    int st, ed;             // 直径端点
    long long diameter_len; // 直径长度
    
    // 重置数组
    void reset() {
        fill(dis, dis + N, INF);
        fill(parent, parent + N, -1);
        fill(visited, visited + N, false);
    }
    
    // ==================== DFS版本（加权树）====================
    int dfs(int u, int fa) {
        dis[u] = 0;
        parent[u] = fa;
        int farthest_node = u;
        
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (v == fa) continue;
            
            int leaf = dfs(v, u);
            long long len = dis[v] + e[i].w;
            
            if (len > dis[u]) {
                dis[u] = len;
                farthest_node = leaf;
            }
        }
        
        return farthest_node;
    }
    
    // 两遍DFS求直径（支持加权树）
    long long get_diameter_dfs(int start_node = 1) {
        reset();
        st = dfs(start_node, 0);      // 第一遍找端点st
        
        reset();
        ed = dfs(st, 0);              // 第二遍从st找ed
        diameter_len = dis[ed];
        
        return diameter_len;
    }
    
    // ==================== BFS版本（仅限边权=1）====================
    int bfs(int start) {
        reset();
        queue<int> q;
        q.push(start);
        dis[start] = 0;
        parent[start] = -1;
        
        int farthest_node = start;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            visited[u] = true;
            
            for (int i = head[u]; i; i = e[i].next) {
                int v = e[i].to;
                if (visited[v]) continue;
                
                dis[v] = dis[u] + e[i].w;
                parent[v] = u;
                q.push(v);
                
                if (dis[v] > dis[farthest_node]) {
                    farthest_node = v;
                }
            }
        }
        
        return farthest_node;
    }
    
    // BFS求直径（仅限边权为1）
    long long get_diameter_bfs(int start_node = 1) {
        st = bfs(start_node);
        ed = bfs(st);
        diameter_len = dis[ed];
        return diameter_len;
    }
    
    // ==================== Dijkstra版本（支持任意权重）====================
    void dijkstra(int start) {
        reset();
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        dis[start] = 0;
        pq.push({0, start});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d != dis[u]) continue;
            
            for (int i = head[u]; i; i = e[i].next) {
                int v = e[i].to;
                if (dis[v] > d + e[i].w) {
                    dis[v] = d + e[i].w;
                    parent[v] = u;
                    pq.push({dis[v], v});
                }
            }
        }
    }
    
    // 两遍Dijkstra求直径（支持任意权重）
    long long get_diameter_dijkstra(int start_node = 1) {
        // 第一遍：从起点找最远点
        dijkstra(start_node);
        st = max_element(dis + 1, dis + n + 1) - dis;
        
        // 第二遍：从st点求直径
        dijkstra(st);
        ed = max_element(dis + 1, dis + n + 1) - dis;
        diameter_len = dis[ed];
        
        return diameter_len;
    }
    
    // ==================== 路径和辅助函数 ====================
    // 获取直径路径
    vector<int> get_diameter_path() {
        vector<int> path;
        int u = ed;
        while (u != -1 && u != 0) {
            path.push_back(u);
            u = parent[u];
        }
        reverse(path.begin(), path.end());
        return path;
    }
    
    // 获取所有节点到直径的最小距离
    vector<long long> get_min_dist_to_diameter() {
        vector<int> diameter_path = get_diameter_path();
        vector<long long> min_dist(n + 1, INF);
        
        // 预处理直径上点到其他点的距离
        for (int u : diameter_path) {
            reset();
            dijkstra(u);
            for (int i = 1; i <= n; i++) {
                min_dist[i] = min(min_dist[i], dis[i]);
            }
        }
        
        return min_dist;
    }
    
    // 智能选择算法
    long long get_diameter(int start_node = 1) {
        // 检查边权是否都是1
        bool all_weight_one = true;
        for (int i = 1; i <= cnt; i++) {
            if (e[i].w != 1) {
                all_weight_one = false;
                break;
            }
        }
        
        if (all_weight_one && n <= 100000) {
            // 小规模+边权为1，用DFS更快
            return get_diameter_dfs(start_node);
        } else if (all_weight_one) {
            // 大规模+边权为1，避免递归深度问题
            return get_diameter_bfs(start_node);
        } else {
            // 有加权边，使用Dijkstra
            return get_diameter_dijkstra(start_node);
        }
    }
};

// ==================== 测试和示例 ====================
void test_different_weights() {
    cout << "===== 测试不同边权情况 =====\n";
    
    // 重置图
    memset(head, 0, sizeof(head));
    cnt = 0;
    
    // 例子：加权树
    // 1-2(3), 2-3(2), 2-4(4), 3-5(1), 4-6(2)
    vector<tuple<int, int, long long>> edges = {
        {1, 2, 3}, {2, 3, 2}, {2, 4, 4}, {3, 5, 1}, {4, 6, 2}
    };
    
    n = 6;
    for (auto [u, v, w] : edges) {
        add_edge(u, v, w);
    }
    
    TreeDiameterAdvanced<> solver;
    
    // 测试DFS
    long long dfs_result = solver.get_diameter_dfs(1);
    cout << "DFS版本直径长度: " << dfs_result << "\n";
    auto dfs_path = solver.get_diameter_path();
    cout << "DFS路径: ";
    for (int x : dfs_path) cout << x << " ";
    cout << "\n";
    
    // 测试Dijkstra
    long long dijk_result = solver.get_diameter_dijkstra(1);
    cout << "Dijkstra版本直径长度: " << dijk_result << "\n";
    auto dijk_path = solver.get_diameter_path();
    cout << "Dijkstra路径: ";
    for (int x : dijk_path) cout << x << " ";
    cout << "\n";
    
    // 智能选择
    long long smart_result = solver.get_diameter(1);
    cout << "智能选择结果: " << smart_result << "\n\n";
}

void test_unweighted_tree() {
    cout << "===== 测试无权树情况 =====\n";
    
    // 重置图
    memset(head, 0, sizeof(head));
    cnt = 0;
    
    // 例子：无权树
    // 1-2, 2-3, 2-4, 3-5, 4-6
    vector<pair<int, int>> edges = {
        {1, 2}, {2, 3}, {2, 4}, {3, 5}, {4, 6}
    };
    
    n = 6;
    for (auto [u, v] : edges) {
        add_edge(u, v, 1);
    }
    
    TreeDiameterAdvanced<> solver;
    
    // BFS版本
    long long bfs_result = solver.get_diameter_bfs(1);
    cout << "BFS版本直径长度: " << bfs_result << "\n";
    auto bfs_path = solver.get_diameter_path();
    cout << "BFS路径: ";
    for (int x : bfs_path) cout << x << " ";
    cout << "\n";
    
    // DFS版本
    long long dfs_result = solver.get_diameter_dfs(1);
    cout << "DFS版本直径长度: " << dfs_result << "\n";
    
    // Dijkstra版本
    long long dijk_result = solver.get_diameter_dijkstra(1);
    cout << "Dijkstra版本直径长度: " << dijk_result << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 运行测试
    test_different_weights();
    test_unweighted_tree();
    
    cout << "===== 根据边权智能选择算法的建议 =====\n";
    cout << "1. 边权都为1 & n<=1e5: 使用DFS（速度最快）\n";
    cout << "2. 边权都为1 & n>1e5: 使用BFS（避免栈溢出）\n";
    cout << "3. 有加权边: 使用Dijkstra（保证正确性）\n";
    cout << "4. 不确定情况: 使用智能选择方法 get_diameter()\n\n";
    
    return 0;
}

目录

树的直径定义

两次dfs法求直径

证明

代码实现

DP求树的直径

树的所有直径拥有相同的中点

证明

推论与应用

代码验证

树的直径的重合部分

证明

直观理解

应用：NOI2013 快餐店

相关题目

总结

直径必过边

两次 dfs 法

DP 法

参考