\(O(n^2)\)的\(DP\)很容易想，\(f[u][i]\)表示在\(u\)的子树中距离\(u\)为\(i\)的点的个数，则\(f[u][i]=\sum f[v][i-1]\)

长链剖分。

\(O(1)\)继承重儿子的信息，再暴力合并其他轻儿子的信息，时间复杂度是线性的。

继承重儿子用指针实现，非常巧妙。

#include 
    
     int xjc; char ch;inline int read(){    xjc = 0; ch = getchar();    while(ch < '0' || ch > '9') ch = getchar();    while(ch >= '0' && ch <= '9'){ xjc = xjc * 10 + ch - '0'; ch = getchar(); }    return xjc;}const int MAXN = 1000010;struct Edge{    int next, to;}e[MAXN << 1];int head[MAXN], num, son[MAXN], len[MAXN], *f[MAXN], tmp[MAXN], *id = tmp, ans[MAXN], n;inline void Add(int from, int to){    e[++num].to = to; e[num].next = head[from]; head[from] = num;    e[++num].to = from; e[num].next = head[to]; head[to] = num;}void dfs(int u, int fa){    for(int i = head[u]; i; i = e[i].next)       if(e[i].to != fa){         dfs(e[i].to, u);         if(len[e[i].to] > len[son[u]])           son[u] = e[i].to;       }    len[u] = len[son[u]] + 1;}void dp(int u, int fa){    f[u][0] = 1;    if(son[u]) f[son[u]] = f[u] + 1, dp(son[u], u), ans[u] = ans[son[u]] + 1;    for(int i = head[u]; i; i = e[i].next)       if(e[i].to != fa && e[i].to != son[u]){         f[e[i].to] = id; id += len[e[i].to]; dp(e[i].to, u);         for(int j = 1; j <= len[e[i].to]; ++j){            f[u][j] += f[e[i].to][j - 1];            if(f[u][j] > f[u][ans[u]] || f[u][j] == f[u][ans[u]] && j < ans[u])              ans[u] = j;         }       }    if(f[u][ans[u]] == 1) ans[u] = 0;}int main(){    n = read();    for(int i = 1; i < n; ++i)       Add(read(), read());    dfs(1, 0); f[1] = id; id += len[1];    dp(1, 0);    for(int i = 1; i <= n; ++i)       printf("%d\n", ans[i]);    getchar();}