树的直径详解：定义、性质与求解方法
树的直径详解：定义、性质与求解方法
树的直径是图论中的一个重要概念，它指的是树上任意两点之间的最长简单路径。本文将从定义出发，详细探讨树的直径的性质，并介绍三种不同的求解方法：Floyd算法、两遍DFS和树形DP。
定义
树上任意两点之间的最长简单路径即为「树的直径」。
性质
树的直径不一定唯一。
举个例子，比如说有这么一棵树：
假设这张图中每一条边边权均为1，那么手动推算一下，发现直径有：
2 -> 1 -> 4 -> 5
，
3 -> 1 -> 4 -> 6
（自己手动去推，这里就不一一例举了）……树的直径的端点一定是深度为1的点。
对于这种图论的知识点还是先画张图（边权都是1）：
现在我们找的点对是( 2 , 4 )，假设( 2 , 4 )是这棵树的直径。
但是，2/4除了两个点向连接的那条边之外，2还连接了1/3，4连接了5/6。显然还能继续拓展，可以证明，( 2 , 4 )一定不是树的直径。树的直径若有多条，那么所有的树的直径一定交汇于1个或2个点。这1个或2个点即为「树的中心」。
我们采用反证法进行证明：
假设两条直径( A , B )，( C , D )互不相交，因为树是联通的，所以一定存在一条路径连接这两条直径上的点。我们设( A , B )上某一个点为x，( C , D )上某一个点为y。
现在，我们从A出发，依次经过x、y到达D。显然，新路径比( A , B )要长，与( A , B )为直径互相矛盾，所以假设不成立。
不过，需要注意上面假设成立的条件是：不存在3个以上的连续的边权为0的路径。
比如说下面这张图：
假设我们选择路径( 1 , 2 )与( 5 , 4 )，这两条路径没有相交且均为「树的直径」，这种情况下，假设失效。树上任意点i，距离其最远的点x，一定是树的直径的某个端点。
同样采用反证法，假设x不是直径的某个端点，那么存在一条从i开始的路径，比从i到x要更长。
矛盾点就在于，如果x不为直径的某个端点，那么i到x的路径不可能是最长的路径。但是根据x的定义，x是距离i最远的点。意味着i到x的路径是树的最长路径之一，显然假设不成立。
所以，x一定是树的直径的某个端点。
解法
解法1：Floyd
先运行一遍 Floyd，然后找出最长路径的长度。
时间复杂度O ( n^3 )，效率低下。
解法2：两遍 DFS
第一遍，我们从任意一点开始跑 DFS。为了方便，我们通常选择从1节点开始跑。
求出距离其最远的点x。
然后，从x开始跑第二遍 DFS。找出距离其最远的点y，顺带求出直径的长度。
时间复杂度O ( n )，比较优秀。
解法3：树形 DP
在上面 DFS 的解法中，你可能会发现一个问题：解法2跑不了负边权。
Hack
Input：
9
1 2 -3
1 3 1
2 4 -7
4 5 4
4 6 -2
6 7 -3
7 8 -9
7 9 3
Output:
5
我们需要找出一条最长链和一条次长链，且最长链和次长链互不相交。
求出从任意节点出发，最长链的长度和次长链的长度。
用树形 DP 来维护就行了。
例题：B4016 树的直径
两遍 DFS 解法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,sum,id;
vector<int>v[100005];
void dfs(int x,int fa,int len){
if(len>=sum){
sum=len,id=x;
}
for(auto z:v[x]){
if(z!=fa){
dfs(z,x,len+1);
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,-1,0);
dfs(id,-1,0);
cout<<sum;
return 0;
}
树形 DP 解法
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dp[200005],ans=-1e18,dp1[200005];
vector<int>v[200005];
void dfs(int x,int fa){
for(auto z:v[x]){
if(z!=fa){
dfs(z,x);
if(dp[x]<=dp[z]+1){
dp1[x]=dp[x];
dp[x]=dp[z]+1;
}else if(dp1[x]<=dp[z]+1){
dp1[x]=dp[z]+1;
}
}
}
ans=max(ans,dp[x]+dp1[x]);
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,-1);
cout<<ans;
return 0;
}