换根dp

ABC428 E

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
#define debug(x) cerr<<#x<<":"<<x<<"\n";
#define debugv(v) cerr<<#v<<":\n";for(int i=0;i<v.size();i++) cerr<<v[i]<<" ";cerr<<"\n";
int n;
const int N=5e5+10;
vector<int> a[N];
int d[N],cnt[N],ans[N];
void dfs1(int u,int fa){
    cnt[u]=u;
    for(auto v:a[u]){
        if(v==fa) continue;
        dfs1(v,u);
        if(d[v]+1>d[u]) d[u]=d[v]+1,cnt[u]=cnt[v];
        else if(d[v]+1==d[u]&&cnt[v]>cnt[u]) cnt[u]=cnt[v];
    }
}
int nd[N],ncnt[N];//父链
void dfs2(int u,int fa){
    ans[u]=cnt[u];
    if(!ncnt[u])ncnt[u]=u;
    set<pii> s;
    for(auto v:a[u]){
        if(v==fa) continue;
        s.insert({d[v],cnt[v]});
    }
    for(auto v:a[u]){
        if(v==fa) continue;
        //更新父链
        s.erase({d[v],cnt[v]});   
        int prex=nd[u],prey=ncnt[u];
        if(s.size()){
            auto it=s.rbegin();
            auto [dis,tmp]=*it;
            if(dis+1>nd[u]) nd[u]=dis+1,ncnt[u]=tmp;
            else if(dis+1==nd[u]&&tmp>ncnt[u]) ncnt[u]=tmp;
        }
        s.insert({d[v],cnt[v]});
        nd[v]=nd[u]+1,ncnt[v]=ncnt[u];
        //更新儿子
        if(nd[u]+1>d[v]) d[v]=nd[u]+1,cnt[v]=ncnt[u];
        else if(nd[u]+1==d[v]&&ncnt[u]>cnt[v]) cnt[v]=ncnt[u];
        dfs2(v,u);
        //还原父链
        nd[u]=prex,ncnt[u]=prey;
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    // debug("hello")
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}