Template. Heavy-light Decomposition

第一次DFS，son()：先紀錄所有點的子節點（含）數目、深度等資訊。
第二次DFS，build()：依據上次DFS的結果，優先選擇子節點最多的點構成重鏈。

#define maxn 100001
struct node {
    int size, max_son, parent, dep;
}n[maxn];
int link_top[maxn], link[maxn];
int global_time = 0;
vector<int> tree[maxn];
void son(int now, int p) {
    node &cur = n[now];
    cur.size = 1;
    cur.max_son = -1;
    for (int i : tree[now]) {
        if (i == p)
            continue;
        n[i].parent = now;
        n[i].dep = cur.dep + 1;
        son(i, now);
        if (cur.max_son == -1 || n[i].size > n[cur.max_son].size)
            cur.max_son = i;
        cur.size += n[i].size;
    }
}
void build(int now, int top) {
    link[now] = ++global_time;
    link_top[now] = top;
    if (n[now].size == 1)
        return;
    build(n[now].max_son, top);
    for (int i : tree[now]) {
        if (i == n[now].max_son || i == n[now].parent)
            continue;
        build(i, i);
    }
}
int lca(int a, int b) {
    int ta = link_top[a];
    int tb = link_top[b];
    while (ta != tb) {
        if (n[ta].dep < n[tb].dep) {
            swap(ta, tb);
            swap(a, b);
        }
        ta = link_top[a = n[ta].parent];
    }
    return n[a].dep < n[b].dep ? a : b;
}