CF竞赛题目讲解_CF161D(树上启发式合并)

// https://codeforces.com/problemset/problem/161/D

// CF竞赛题目讲解_CF161D(树上启发式合并)

程序中例子：

5 2

1 2

2 3

3 4

2 5

int sz[maxn], son[maxn],dep[maxn];

int cnt[maxn];// 已经处理节点中深度为dep的节点个数

int dfsn[maxn],T=0;

int a[maxn];//dfs序 编号对应的原标号

void dfs(int s, int pre) {

    sz[s] = 1;// 子树大小

dep[s] = dep[pre] + 1;// 节点深度

dfsn[s]=++T; //dfs序 编号

a[T]=s; //dfs序 编号对应的原标号

    for(auto e : load[s]) {

        if(e == pre)   continue;

        dfs(e, s);

        sz[s] += sz[e];

        if(sz[e] > sz[son[s]])

            son[s] = e;// 重子树

    }

}