树的直径算法详解：从基础概念到实战应用
树的直径算法详解：从基础概念到实战应用
树的直径是图论中的一个重要概念，它表示一棵树中最长的一条简单路径。本文将详细介绍三种求解树的直径的算法：暴力算法、DFS直接求解和树形DP，并通过具体例题帮助读者巩固所学知识。
树的直径是什么
这是一棵图论中的树：
这棵树的直径就是这棵树中最长的一条简单路径。
树的直径怎么求
暴力算法
直接对每个点进行 DFS，找到每个点离最远的点的距离，最后求出最长的一条路，也就是树的直径。
时间复杂度：O(n^2)
代码示例：
void dfs(int x, int fa, int sum) {
dis[x] = sum;
for (auto i : v[x]) {
if (i == fa) continue;
dfs(i, x, sum + 1);
}
return;
}
DFS直接求
直接说结论：
对于每一个点x，离x最远的点一定是树的直径的一个顶点。
为什么呢？我们可以用反证法来推导：
假设树的直径的端点为u和v，设对于每一个离点x最远的点y不是树的直径的端点u和v，按我们可以分类讨论：
- 点x在树的直径u→v中
- 点x不在树的直径u→v中，但x→y这条路径与树的直径u→v有一部分重合。
- 点x不在树的直径u→v中，且x→y这条路径与树的直径u→v完全不重合。
先来看情况1，若点x在树的直径u→v中且点y既不等于u也不等于v。因为y既不等于u也不等于v，那么dis(x→y)必定会大于dis(x→u)和dis(x→v)，因为dis(u→v) = dis(u→x) + dis(x→v)，又因为dis(x→v) < dis(x→y)，那么此时这棵树的直径便是u→y这两条路，与直径的定义不符，所以错误。
再来看情况2，点x不在树的直径u→v中，但x→y这条路径与树的直径u→v有一部分重合。这里又可以分成两种情况。
- x→y被完全包含在u→v内，这是显然不可能的。
- x→y有一部分包含在u→v内，那我们可以设点o为公共部分其中的一个点，那么此时dis(o→y)一定要大于dis(o→v)和dis(o→u)，与直径的定义不符，所以错误。
最后来看情况3，点x不在树的直径u→v中，且x→y这条路径与树的直径u→v完全不重合。
这时，我们设点o于u→v内，因为每棵树都是连通的，所以必定有一条x→o路。于是，就得到了一下式子：
dis(u→v) = dis(u→o) + dis(o→v) = dis(u→o) + dis(x→v) - dis(x→o)
dis(u→y) = dis(u→o) + dis(o→y) = dis(u→o) + dis(x→y) - dis(x→o)
将两个式子互相抵消，分别得到dis(x→v)和dis(x→y)，因为dis(x→y) > dis(x→v)，所以得到dis(u→v) < dis(u→y)，与直径的定义不符，所以错误。
至此，证毕。
于是！我们可以从点1开始 DFS，找到离点1最远的点y，再进行 DFS 找到离点y最远的点，就找到了树的直径。
代码示例：
#include <bits/stdc++.h>
using namespace std;
int dis, pos;
vector<int> v[100010];
void dfs(int x, int fa, int sum) {
if (sum >= dis) {
dis = sum;
pos = x;
}
for (auto i : v[x]) {
if (i == fa) continue;
dfs(i, x, sum + 1);
}
return;
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, -1, 0);
dis = 0;
dfs(pos, -1, 0);
cout << dis << endl;
return 0;
}
该模版写法不一，也可以用dis数组存储距离，DFS 完后再找最大的路径。该带码也同样适用于带边权的树。
时间复杂度：O(n)。
注意：该算法只能在所有边权为正数的情况下成立，否则会出问题，具体为什么下面会讲。
我们来看这张图：
不难发现，这棵树的直径是5→6这一条路，但是如果你从点1开始进行 DFS，只能找到点3，因为中间被2→4这条边挡住了，从1→5不是最优解。
树形DP
树形DP的写法。dp_x表示从x出发走向x的子树中最长的一条路径。
假设有一棵树的根节点为root（我们这里称把x的子节点称作为x_i），那么我们的dp_root就表示从root节点出发能走到的最远距离，也就是root的子树的最大的深度。所以，我们得要从子树开始更新，也就是在这里：
for (auto i : v[x]) {
if (i.x == fa) continue;
dfs(i.x);
dp[x] = ...;
}
那么，我们就可以在遍历子节点v_i的时候更行新dp_root：
dp_root = max(dp_root, dp_vi + dis_root→vi)
其他节点也同理。
这时，有聪明的读者就会说了：你这不是只更新了它的一个子树吗，如果树的直径是这样子，那你的 DP 不是就错了吗？
读者说的没错，我们要考虑图片上的情况。
我们可以设置一个中间节点，比如这张图的中间点就是root节点，一条路径可以贯穿一个中间节点的两个子树，而我们的dp数组只记录了一个子树的最大的深度，也就是子树的最长路。
于是，我们可以在更新dp数组的时候同时更新另一个变量ans_x，表示若x为树的直径的中间点，穿过x最长的路径的长度。当然，dp数组也不能落下，但是答案还是存在ans数组里。因为要找到两个长度最大的长度，所以更新代码为这样：
ans_x = max(ans_x, dp_x + dp_vi + dis_x→vi)
至于为什么是dp_x + dp_vi 因为此时的dp_x表示的是在vi之前遍历到的子树的最大值，dp_vi + dis_x→vi表示这棵子树的最大的长度，所以，ans数组的更新应该在dp数组的更新之前。
代码（只展示 DFS 部分）：
void dfs(int x, int fa) {
dp[x] = 0;
for (auto i : v[x]) {
if (i.x == fa) continue;
dfs(i.x, x);
ans[x] = max(ans[x], dp[x] + dp[i.x] + i.w)
dp[x] = max(dp[x], dp[i.x] + i.w);
}
}
例题
T1.P8602 [蓝桥杯 2013 省 A] 大臣的旅费
题目描述
很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x - 1千米到第x千米这一千米中（x是整数），他花费的路费是x + 10这么多。也就是说走1千米花费11，走2千米要花费23。
J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
思路+代码
这道题乍一看上去确实很乱，但我们可以找找关键句。
如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。这句话的意思不就是从根节点出发到每一个节点的路径唯一吗？
他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？这句话不就是要求一棵树上最长的一条路径吗？
综上所述，这道题完完全全就是树的直径的板子，只是读题困难一点而已。需要注意，最后的答案并不是树的直径的长度，而是像题目描述中的这样：
cout << dis * 10 + (dis + 1) * dis / 2 << endl;
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dis, pos;
struct ll {
int x, w;
};
vector<ll> v[100010];
void dfs(int x, int fa, int sum) {
if (sum >= dis) {
dis = sum;
pos = x;
}
for (auto i : v[x]) {
if (i.x == fa) continue;
dfs(i.x, x, sum + i.w);
}
return;
}
signed main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y, w;
cin >> x >> y >> w;
v[x].push_back({y, w});
v[y].push_back({x, w});
}
dfs(1, -1, 0);
dis = 0;
dfs(pos, -1, 0);
cout << dis * 10 + (dis + 1) * dis / 2 << endl;
return 0;
}
难度：1 / 5。
T2.HDU 2196 Computer
请注意，这道题不是洛谷的，需要在 vjudge 上交代码。
题目描述
给定一棵节点为N的树（1 ≤ N ≤ 10^4），输出每个节点i离i最远的节点的长度。
思路+代码
首先，O(N^2)的暴力 DFS 是不可能的，因为题目中还有T组数据。想一想，对于每个节点i离i最远的点是什么呢？
对的，之前说过，就是树的直径的两个端点！所以离每一个节点i最远的点就是树的直径的两端的节点u和v。
于是，我们可以用O(N)的 DFS 先将树的直径的两个端点求出来，在继续用O(N)的 DFS 求出对每个节点的距离，对于节点i，它的答案就是：
max(dis_u→i, dis_v→i)
代码：
#include <bits/stdc++.h>
using namespace std;
int dis[100010], n;
bool f[100010];
struct ll {
int x, w;
};
vector<ll> v[100010];
void dfs(int x, int sum) {
dis[x] = max(dis[x], sum);
f[x] = true;
for (int i = 0; i < v[x].size(); i++) {
ll tmp = v[x][i];
if (f[tmp.x]) continue;
dfs(tmp.x, sum + tmp.w);
}
return;
}
void solve() {
memset(dis, 0, sizeof(dis));
memset(f, false, sizeof(f));
for (int i = 1; i <= n; i++) {
v[i].clear();
}
for (int i = 1; i < n; i++) {
int x, w;
cin >> x >> w;
v[i + 1].push_back({x, w});
v[x].push_back({i + 1, w});
}
dfs(1, 0);
int mx = -1e9, pos = -1, pos2 = -1;
for (int i = 1; i <= n; i++) {
pos = (dis[i] >= mx ? i : pos);
mx = max(mx, dis[i]);
}
memset(dis, 0, sizeof(dis));
memset(f, false, sizeof(f));
dfs(pos, 0);
mx = -1e9;
for (int i = 1; i <= n; i++) {
pos2 = (dis[i] >= mx ? i : pos2);
mx = max(mx, dis[i]);
}
memset(f, false, sizeof(f));
dfs(pos2, 0);
for (int i = 1; i <= n; i++) {
cout << dis[i] << '\n';
}
}
int main() {
while (cin >> n) {
solve();
}
return 0;
}
难度：3 / 5。
作业
- B4016 树的直径，模板题，难度：1 / 1。
- P3304 [SDOI2013] 直径，难度：3 / 5。
- P4408 [NOI2003] 逃学的小孩，难度4 / 5。