【筆記】Lowest Common Ancestor 最近共同祖先

//從根節點DFS遍歷整棵樹，可以求得每個節點的層數 (depth)
//及其子樹包含的節點個數 (size)。
int dfs(int node, int d){
    dep[node] = d + 1;
    if (v[node].empty()){
        siz[node] = 1;
        return 1;
    }
    int total = 1;
    for (int i:v[node]){
        total += dfs(i, d+1);
    }
    siz[node] = total;
    return siz[node];
}

// 找出每個節點的 2^i 倍祖先
// 2^20 = 1e6 > 200000
for (int i = 1; i < 20; i++){
    for (int j = 1; j <= n; j++){
        p[j][i] = p[p[j][i-1]][i-1];
    }
}

// 求兩點的LCA（利用倍增法）
int lca(int a, int b){
    if (dep[b] < dep[a]) swap(a, b);
    if (dep[a] != dep[b]){
        int dif = dep[b] - dep[a];
        for (int i = 0; i < 20; i++){
            if (dif & 1) b = p[b][i];
            dif >>= 1;
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--){
        if (p[a][i] != p[b][i]){
            a = p[a][i];
            b = p[b][i];
        }
    }
    return p[a][0];
}