题解：AT_abc428_e [ABC428E] Farthest Vertex

OneLeft · 2025-10-19 10:03:53 · 题解

题意

给定一棵大小为 n 的树，对于树上的每一个节点求与节点距离最远的节点编号，有多个距离相等则返回较大的那个。

解法

考虑树上动态规划，设 f_{u,0/1} 为在以 u 为根的子树中，离节点 u 最远的节点的距离和编号，转移方程如下：

• 设 v 为 u 的子节点，若 f_{v,0}+1>f_{u,0} 或 f_{v,0}+1=f_{u,0} 且 f_{v,1}>f_{u,1}，则 f_{u,0}\gets f_{v,0}+1，f_{u,1}\gets f_{v,1}。

然后考虑换根即可。

代码

#include<bits/stdc++.h>
#define mkp make_pair
using namespace std;
const int N=5e5+5;
vector<int>edge[N];
void build(int u,int v){edge[u].push_back(v);}
pair<int,int>f[N];
void get_f(int u,int fa)
{
    f[u]={0,u};
    for(int v:edge[u])
    {
        if(v==fa)continue;
        get_f(v,u);
        pair<int,int>tmp={f[v].first+1,f[v].second};
        if(f[u]<tmp)f[u]=tmp;
    }
}
int ans[N];
void get_ans(int u,int fa)
{
    f[u]={0,u};
    pair<int,int>maxn;
    for(int v:edge[u])
    {
        pair<int,int>tmp={f[v].first+1,f[v].second};
        if(tmp>f[u])maxn=f[u],f[u]=tmp;
        else if(tmp>maxn)maxn=tmp;
    }
    ans[u]=f[u].second;
    for(int v:edge[u])
    {
        if(v==fa)continue;
        pair<int,int>t=f[u],tmp={f[v].first+1,f[v].second};
        if(f[u]==tmp)f[u]=maxn;
        get_ans(v,u);
        f[u]=t;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1,u,v;i<n;i++)cin>>u>>v,build(u,v),build(v,u);
    get_f(1,0),get_ans(1,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    return 0;
}