给定一棵无根数，要求给出距离各个节点的最远节点，若有多个则给出编号最大的。

这道题蛮简单的，但是赛时吃了两发罚时。

首先，我们求这棵树的欧拉序，这可以通过以下代码来完成。

void dfs(int u,int fa){
    dep[u]=dep[fa]+1,eux[++tot]=u,lf[u]=tot;
    for(int v:tr[u]) if(v!=fa) dfs(v,u),eux[++tot]=u;
    rt[u]=tot;
}

写出这个东西，是为了便于迅速地将子树内的深度加上或减去一个固定值。为了实现这个，我们写线段树，来保存欧拉序对应位置上的深度，以及求出深度最大编号的东西。

最后，我们再跑一遍 dfs，边跑边修改欧拉序，然后就完了。

// Atcoder ABC428E - Farthest Vertex
// Alea
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,dep[N],eux[N<<4],lf[N],rt[N],tot;
int mxs[N<<4],num[N<<4],lazy[N<<4];
void pushdown(int u){
    mxs[u<<1]+=lazy[u],mxs[u<<1|1]+=lazy[u];
    lazy[u<<1]+=lazy[u],lazy[u<<1|1]+=lazy[u];
    lazy[u]=0;
}
void pushup(int u){
    if(mxs[u<<1]==mxs[u<<1|1]) num[u]=max(num[u<<1],num[u<<1|1]),mxs[u]=mxs[u<<1];
    else{
        if(mxs[u<<1]<mxs[u<<1|1]) num[u]=num[u<<1|1],mxs[u]=mxs[u<<1|1];
        else num[u]=num[u<<1],mxs[u]=mxs[u<<1];
    }
}
void build(int u,int L,int R){
    if(L==R) mxs[u]=dep[eux[L]],num[u]=eux[L];
    else{
        int M=L+((R-L)>>1);
        build(u<<1,L,M),build(u<<1|1,M+1,R);
        pushup(u);
    }
}
void modify(int u,int L,int R,int ql,int qr,int v){
    if(ql<=L&&R<=qr) mxs[u]+=v,lazy[u]+=v;
    else{
        pushdown(u);
        int M=L+((R-L)>>1);
        if(ql<=M) modify(u<<1,L,M,ql,qr,v);
        if(M<qr) modify(u<<1|1,M+1,R,ql,qr,v);
        pushup(u);
    }
}
int get(int u,int L,int R,int x){
    if(L==R) return mxs[u];
    else{
        int M=L+((R-L)>>1);pushdown(u);
        return (x<=L?get(u<<1,L,M,x):get(u<<1|1,M+1,R,x));
    }
}
vector<int> tr[N];
void adde(int u,int v){
    tr[u].push_back(v),tr[v].push_back(u);
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1,eux[++tot]=u,lf[u]=tot;
    for(int v:tr[u]) if(v!=fa) dfs(v,u),eux[++tot]=u;
    rt[u]=tot;
}
int ans[N];
void chge(int u,int x){
    modify(1,1,tot,1,lf[u]-1,x),modify(1,1,tot,rt[u]+1,tot,x),modify(1,1,tot,lf[u],rt[u],-x);
}
void dfs_(int u,int fa){
    ans[u]=num[1];
    for(int v:tr[u]) if(v!=fa) chge(v,1),dfs_(v,u),chge(v,-1);
    assert(ans[u]==num[1]);
}
int main(){
    cin>>n;
    for(int i=1,u,v;i<n;++i) cin>>u>>v,adde(u,v);
    dfs(1,0),build(1,1,tot),dfs_(1,0);
    for(int i=1;i<=n;++i) cout<<ans[i]<<endl;
    return 0;
}

EOF