题解：AT_abc428_e [ABC428E] Farthest Vertex

· · 题解

题意：

给你边权为 1 的一棵树，问这棵树上每个点距离最远的点最大编号。

思路：

很容易想到树的 直径 。
由树直径的定义：

答案一定是直径的两个端点之一。（定义直径的端点为 s，t ）

  1. 节点 u 在直径上：

假设距离点 u 最远的点是 v 。
如果 v 不是 s 或者 t 那么s \to t 就不是直径了。

  1. 节点 u 不在直径上:

很明显，既然 u 不在直径上了，那么从那个分开的结点到 t 一定优于到 u ，u 只有去搭上直径才是最优的 ，其答案等于直径上距离最近的点的答案。

所以写起来就明了了：

找到直径，再维护一个所有点到根的距离 dis ，用 dis_{u,v}=dis_{1,u}+dis_{1,v}-2 \times dis_{1,lca(u,v)} 来判断取哪一个直径。

一点细节：

注意到要取编号最大的点，那么维护直径时记得判断编号。

还有不要直接对每个点作 lca 再判断。（我写T了）
可以利用直径上点搜到的非直径部分和该点的答案相同，再搜一遍直接处理答案。

时间复杂度： O(n\log n)。 找直径 + 倍增求 lca 。

代码：

/*
雲璃猫猫が好きです
すべての生命よ,歌のように輝いています
截剣式、斬、断、破です!
*/
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define INF 1e18
#define lb long double
#define ls (id<<1)
#define rs (id<<1|1)
#define rep(i,l,r,k) for(int i=(l);i<=(r);i+=(k))
#define dep(i,r,l,k) for(int i=(r);i>=(l);i-=(k))
#define tep(x,y) for(auto x:y)
#define wl while
#define mk(a,b) make_pair(a,b)
#define me(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define pr putchar
#define fi first
#define se second
#define max(a,b)((a)>(b)?(a):(b))
#define min(a,b)((a)<(b)?(a):(b))
using namespace std;
random_device rd;
unsigned int seed=rd();
mt19937 Rand(seed);
typedef pair<int,int> pii;
const int M=5e5+110,mod=1e9+7,Mod=998244353;
__gnu_pbds::gp_hash_table<string,int>ml;
inline int read(){int sum=0,k=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();
    }while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
    }return sum*k;
}inline void wr(int x){if(x<0) putchar('-'),x=-x;
    if(x>9) wr(x/10);return void(putchar(x%10+'0'));}
int n=read(),s,t,dis[M],mx,id,Fa[M][50];//找直径
vector<int>Ed[M];
inline void dfs(int u,int fa,bool ok){
    if(ok){//最后一遍再维护倍增数组
        Fa[u][0]=fa;
        rep(i,1,35,1) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
    }
    for(auto v:Ed[u]){
        if(v==fa) continue;//不往回走
        dis[v]=dis[u]+1;
        //取最大的编号
        if(dis[v]>mx) mx=dis[v],id=v;
        else if(dis[v]==mx) id=max(id,v);
        dfs(v,u,ok);
    }
}
inline int glca(int a,int b){
    //倍增求lca
    if(dis[a]<dis[b]) swap(a,b);
    dep(i,35,0,1) if(dis[Fa[a][i]]>=dis[b]) a=Fa[a][i];
    if(a==b) return a;
    dep(i,35,0,1)
    if(Fa[a][i]!=Fa[b][i]) a=Fa[a][i],b=Fa[b][i];
    return Fa[a][0];
}
int ans[M],vis[M];
inline bool fid(int u,int fa){
    //将直径路上的点打上标记
    if(u==t){
        ans[u]=s;vis[u]=1;
        ans[s]=u;vis[s]=1;
        return 1;//是直径
    }
    for(auto v:Ed[u]){
        if(v==fa) continue;
        if(fid(v,u)){//是直径
            int ds=dis[u]+dis[s]-dis[glca(u,s)]*2,
                dt=dis[u]+dis[t]-dis[glca(u,t)]*2;
            if(ds>=dt) ans[u]=s;
            else ans[u]=t;
            vis[u]=1;
            return 1;
        }
    }return 0;
}
inline void gans(int u,int fa,int wh){
    ans[u]=wh;//维护答案
    for(auto v:Ed[u]){//不搜直径上点
        if(v==fa||vis[v]!=0) continue; 
        gans(v,u,wh);
    }
}
signed main(){
    rep(i,1,n-1,1){
        int u=read(),v=read();
        Ed[u].pb(v);Ed[v].pb(u);
    }
    //找直径
    dfs(1,0,0);s=id;mx=0;id=0;
    dfs(s,0,0);t=id;mx=0;id=0;
    //这里我保证了当s,t距离一样时选s优
    if(s<=t) swap(s,t);
    dfs(1,0,1);
    fid(s,0);
    rep(i,1,n,1)
        if(vis[i]!=0) gans(i,0,ans[i]);
    rep(i,1,n,1) wr(ans[i]),pr(10); 
    return 0;
}