AT_abc428_e 题解

嗯对就是树的直径的性质。

树的直径的性质

对于树上任意一个节点

u

，在所有与

u

存在路径的节点中，距离

u

最远的节点

v

，必定是该树某条直径的两个端点之一。

性质的证明

采用反证法。

首先定义函数

dis(a,b)

表示

a

到

b

之间的距离。

设树的一条直径为

a \to b

（即

dis(a,b)

是树中最大路径长度），任取节点

u

，其最远点为

v

，且

v

既不是

a

也不是

b

。

由于树无环，

u \to v

、

u \to a

、

u \to b

三条路径必然会交于一个公共节点，记为

w

。根据先前定义，

dis(u,v) > dis(u,a)

且

dis(u,v)>dis(u,b)

。

因此，有

dis(v,a) = dis(v,w) + dis(w,a)

，

dis(v,b) = dis(v,w) + dis(w,b)

。由

dis(u,v) > dis (u,a)

，可得

dis(v,w) = dis (u,v) - dis (u,w) > dis (u,a) - dis (u,w) = dis (w,a)

，同理有

dis (v,w) > dis (w,b)

。
代入得

dis (v,a) = dis (v,w) + dis (w,a) > dis (w,a) + dis (w,a)

，而直径

dis (a,b) = dis (w,a) + dis (w,b)

（因为

w

在

a \to b

的路径上）。若

dis (w,a) \ge dis (w,b)

，则

dis (v,a) > dis (w,a) + dis (w,b) = dis (a,b)

，这与 “

a \to b

是树的直径” 矛盾。

故假设不成立，因此

v

必须是直径

a \to b

的端点，即

v

要么是

a

，要么是

b

。

知道了这个东西以后，我们就可以考虑在树上使用两次 DFS 的方法求出某条直径，然后算出两个

dis

数组，判断一下输出即可。

注意这里要求输出编号最大的节点，因此找节点的时候要注意不是随便找一个都行，是要尽可能找编号大的。

CPP

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 5e5+5;
int n,f[N],dis[N],St,Ed;
vector<int> g[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void DFS1(int u,int fa){
    f[u]=f[fa]+1;
    for(int v:g[u])
        if(v^fa)DFS1(v,u);
    return;
}
void DFS2(int u,int fa){
    dis[u]=dis[fa]+1;
    for(int v:g[u])
        if(v^fa)DFS2(v,u);
    return;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        g[x].pb(y),g[y].pb(x);
    }DFS1(1,0);
    for(int i=1;i<=n;i++)
        if(f[i]>=f[St])St=i;
    memset(f,0,sizeof(f));
    DFS1(St,0);
    for(int i=1;i<=n;i++)
        if(f[i]>=f[Ed])Ed=i;
    DFS2(Ed,0);
    for(int x=1;x<=n;x++)
        if(f[x]>dis[x])cout<<St<<"\n";
        else if(f[x]<dis[x])cout<<Ed<<"\n";
        else cout<<max(St,Ed)<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！

文章操作

相关推荐

评论

AT_abc428_e 题解