树的直径解释
树的直径解释
定义
树上任意两点之间的最长简单路径即为「树的直径」。
性质
树的直径不一定唯一。
举个例子,比如说有这么一棵树:
假设这张图中每一条边边权均为1 11,那么手动推算一下,发现直径有:
2 -> 1 -> 4 -> 5
,
3 -> 1 -> 4 -> 6
(自己手动去推,这里就不一一例举了)……树的直径的端点一定是深度为1 11的点。
对于这种图论的知识点还是先画张图(边权都是1 11):
现在我们找的点对是( 2 , 4 ) (2,4)(2,4),假设( 2 , 4 ) (2,4)(2,4)是这棵树的直径。
但是,2 22/4 44除了两个点向连接的那条边之外,2 22还连接了1 11/3 33,4 44连接了5 55/6 66。显然还能继续拓展,可以证明,( 2 , 4 ) (2,4)(2,4)一定不是树的直径。树的直径若有多条,那么所有的树的直径一定交汇于1 11个或2 22个点。这1 11个或2 22个点即为「树的中心」。
我们采用反证法进行证明:
假设两条直径( A , B ) (A,B)(A,B),( C , D ) (C,D)(C,D)互不相交,因为树是联通的,所以一定存在一条路径连接这两条直径上的点。我们设( A , B ) (A,B)(A,B)上某一个点为x xx,( C , D ) (C,D)(C,D)上某一个点为y yy。
现在,我们从A AA出发,依次经过x xx、y yy到达D DD。显然,新路径比( A , B ) (A,B)(A,B)要长,与( A , B ) (A,B)(A,B)为直径互相矛盾,所以假设不成立。
不过,需要注意上面假设成立的条件是:不存在3 33个以上的连续的边权为0 00的路径。
比如说下面这张图:
假设我们选择路径( 1 , 2 ) (1,2)(1,2)与( 5 , 4 ) (5,4)(5,4),这两条路径没有相交且均为「树的直径」,这种情况下,假设失效。树上任意点i ii,距离其最远的点x xx,一定是树的直径的某个端点。
同样采用反证法,假设x xx不是直径的某个端点,那么存在一条从i ii开始的路径,比从i ii到x xx要更长。
矛盾点就在于,如果x xx不为直径的某个端点,那么i ii到x xx的路径不可能是最长的路径。但是根据x xx的定义,x xx是距离i ii最远的点。意味着i ii到x xx的路径是树的最长路径之一,显然假设不成立。
所以,x xx一定是树的直径的某个端点。
解法
解法1:Floyd
先运行一遍 Floyd,然后找出最长路径的长度。
时间复杂度O ( n 3 ) O(n^3)O(n3),效率低下。
解法2:两遍 DFS
第一遍,我们从任意一点开始跑 DFS。为了方便,我们通常选择从1 11节点开始跑。
求出距离其最远的点x xx。
然后,从x xx开始跑第二遍 DFS。找出距离其最远的点y yy,顺带求出直径的长度。
时间复杂度O ( n ) O(n)O(n),比较优秀。
解法3:树形 DP
在上面 DFS 的解法中,你可能会发现一个问题:解法2 22跑不了负边权。
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;
}