题解：AT_abc428_e [ABC428E] Farthest Vertex

题意

给定一棵大小为

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}$ 。

然后考虑换根即可。

代码

CPP

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

题解：AT_abc428_e [ABC428E] Farthest Vertex

文章操作

题意

解法

代码

相关推荐

评论

题解：AT_abc428_e [ABC428E] Farthest Vertex