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

// CF競(jìng)賽題目講解_CF161D(樹上啟發(fā)式合并)

程序中例子：

5 2

1 2

2 3

3 4

2 5

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

int cnt[maxn];// 已經(jīng)處理節(jié)點(diǎn)中深度為dep的節(jié)點(diǎn)個(gè)數(shù)

int dfsn[maxn],T=0;

int a[maxn];//dfs序 編號(hào)對(duì)應(yīng)的原標(biāo)號(hào)

?

void dfs(int s, int pre) {

? ? sz[s] = 1;// 子樹大小

dep[s] = dep[pre] + 1;// 節(jié)點(diǎn)深度

??

dfsn[s]=++T; //dfs序 編號(hào)

a[T]=s; //dfs序 編號(hào)對(duì)應(yīng)的原標(biāo)號(hào)

? ? 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;// 重子樹

? ? }

}