萌新刚学树剖1普朗克时间求吊

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct { int nxt,v; }edge[maxn<<1];
int head[maxn],cnt,n,m,d[maxn];
void addedge(int u,int v) {
    edge[++cnt] = {head[u],v};
    head[u] = cnt;
}
int son[maxn],dfn[maxn],dfc,*dp[maxn],val[maxn],len[maxn],ans[maxn];
int dfs1(int u,int fa) {
    int ml = 0;
    for(int i = head[u];i;i=edge[i].nxt) {
        int v = edge[i].v;
        if(v == fa) continue;
        int vl = dfs1(v,u);
        if(vl > ml) son[u] = v, ml = vl;
    }
    return len[u] = ml + 1;
}
void dfs2(int u,int fa) {
    dfn[u] = ++dfc;
    (dp[u] = val+dfn[u])[0] = 1;
    if(son[u]) dfs2(son[u],u),ans[u] = ans[son[u]] + 1;
    for(int i = head[u];i;i=edge[i].nxt) {
        int v = edge[i].v;
        if(v == son[u] || v == fa) continue;
        dfs2(v,u);
        for(int d = 0;d <= len[v];++d) {
            dp[u][d+1] += dp[v][d];
            if(dp[u][d+1] == dp[u][ans[u]]) ans[u] = min(ans[u],d+1);
            if(dp[u][d+1] > dp[u][ans[u]]) ans[u] = d + 1;
        }
    }
    if(dp[u][ans[u]] == 1) ans[u] = 0;
}
signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i = 1,u,v;i < n;++i) {
        cin>>u>>v;
        addedge(u,v),addedge(v,u);
    }
    dfs1(1,0),dfs2(1,0);
    for(int i = 1;i <= n;++i) cout<<ans[i]<<'\n';
}