F. Dominant Indices 长链剖分-最大d(x, k)

题目链接：https://codeforces.com/problemset/problem/1009/F
题目大意：给你一颗树，用d(x, k)表示x在第k层的儿子（自己为根节点）的节点数量。现在希望你输出每个点取得最大d(x, k)的k，如果多个层相同，取k最小的。

思路；长链剖分的模板题：我们先熟悉一下长链剖分。

解释合并的时候再计算一下答案。

#include <bits/stdc++.h>
using namespace std;
vector<int> G[1000005];

int len[1000005], son[1000005];
int tmp[1000005], *f[1000005], *id=tmp, ans[1000005];
void dfs(int u, int fa){
    for(auto x: G[u]){
        if(x!=fa){
            dfs(x, u);
            if(len[son[u]]<len[x]){// 寻找长儿子
                son[u]=x;
            }
        }
    }
    len[u]=len[son[u]]+1;// 统计 u 的 dep
}

void DP(int u, int fa){
    f[u][0]=1;// 先算上自己
    if(son[u]){
        f[son[u]]=f[u]+1;//共享内存，这样一步之后，f[son[u]][dep]会被自动保存到f[u][dep-1]
        DP(son[u], u);
        ans[u]=ans[son[u]]+1;
    }
    for(auto x: G[u]){
        if(x!=fa&&x!=son[u]){
            f[x]=id; id+=len[x];// 为x节点申请内存，大小等于以x为顶端的长链的长度
            DP(x, u);
            for(int j=1; j<=len[x]; j++){
                f[u][j]+=f[x][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(){
    int n, x, y; scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 0);
    f[1]=id;  id+=len[1];
    DP(1, 0);
    for(int i=1; i<=n; i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}