AT_abc428_e 题解

· · 题解

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

::::success[树的直径的性质]{open} 对于树上任意一个节点 u，在所有与 u 存在路径的节点中，距离 u 最远的节点 v，必定是该树某条直径的两个端点之一。 ::::

::::success[性质的证明] 采用反证法。

首先定义函数 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 数组，判断一下输出即可。

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

#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;
}

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