【树上倍增】最近公共祖先（LCA）

模版题：https://www.luogu.com.cn/problem/P3379

视频讲解1

视频讲解2

某佬题解

思路：

设当前节点为 x x x， f a [ x ] [ i ] fa[x][i] fa[x][i] 代表 x x x 的第 2 i 2^i 2i 个祖先节点，

显然 f a [ x ] [ 0 ] fa[x][0] fa[x][0] 代表 x x x 的直接父节点，

而 f a [ x ] [ i ] fa[x][i] fa[x][i] = f a [ f a [ x ] [ i − 1 ] ] [ i − 1 ] fa[fa[x][i-1]][i-1] fa[fa[x][i−1]][i−1] ， x x x 的 第 2 i 2^i 2i 个祖先节点是 x x x 的第 2 i − 1 2^{i-1} 2i−1 个祖先节点的第 2 i − 1 2^{i-1} 2i−1 个祖先节点（ 2 i 2^i 2i = 2 i − 1 + 2 i − 1 2^{i-1} + 2^{i-1} 2i−1+2i−1）

d e p [ x ] dep[x] dep[x] 数组用来记录 x x x 的深度

f a fa fa 数组需要用 d f s dfs dfs 来求解

void dfs(int u, int pre){

    dep[u] = dep[pre] + 1;
    fa[u][0] = pre;

    for (int i = 1; i <= (lg[dep[u]]); i++) {
        // u 的2^i个祖先是u的2^(i-1)个祖先的2^(i-1)个祖先
        // 2^i = 2^(i-1) + 2^(i-1)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if(j == pre) continue;
        dfs(j, u);
    }
} 
           

预处理

l o g 2 i log_2^i log2i​ 的值

for (int i = 0; i < N; ++i) {
    // lg 8 = lg7 + (1 << 3 == 8)
    lg[i] = lg[i-1] + (1 << (lg[i-1] + 1) == i);
}
           

求解 a a a 和 b b b 的 l c a lca lca 时，需要先 树上倍增 让 a a a 和 b b b 处于同一层，然后如果 a a a 和 b b b 是祖先关系的话，就返回此时的 a a a 和 b b b 中任意的一个；

否则， a a a 和 b b b 同时向上倍增，找到 l c a lca lca 下面一层的节点，此时只需返回 f a [ a ] [ 0 ] fa[a][0] fa[a][0] 和 f a [ b ] [ 0 ] fa[b][0] fa[b][0] （即 a a a和 b b b任意一个的直接父节点）即可！

求证下面代码为何一定能找出 a a a 和 b b b 的 l c a lca lca 的直接子节点 (即 l c a lca lca下面两个节点)

首先此时 a a a 和 b b b 已经处于同一层；

设 d d d = d e p [ a ] dep[a] dep[a];

可以确定 a a a 和 b b b 的 l c a lca lca 的深度（设为 m d md md） 一定在 1 1 1 ~ 2 l o g 2 d = d 2^{log_2^d} = d 2log2d​=d 之间，

l c a lca lca 是 a a a 和 b b b 的第 d − m d d - md d−md 个父节点

设 k k k = l o g 2 d log_2^d log2d​ 即 l g [ d ] lg[d] lg[d]，显然 d d d <= 2 k 2^k 2k，

而 1 1 1 ~ d d d 任何一个数都可以由 2 0 2^0 20, 2 1 2^1 21, 2 2 2^2 22,…, 2 k 2^k 2k 其中的 c c c 个相加求得 !!!（相当于 k k k位二进制凑得 m d md md ） 显然这是肯定的。

然而需要凑得 m d md md - 1 层（即 a a a 的第 d − m d − 1 d - md - 1 d−md−1 个 父节点） 的话，需要将 i = k i = k i=k 从大到小；如果 f a [ a ] [ i ] = = f a [ b ] [ i ] fa[a][i] == fa[b][i] fa[a][i]==fa[b][i]，说明此时跳的话，会跳过头

d − m d − 1 d - md - 1 d−md−1 一定小于当前的 2 i 2^i 2i，

所以 d − m d − 1 d - md - 1 d−md−1 一定能由 { 0 ∣ 1 } \{0 | 1\} {0∣1} * 2 i − 1 2^{i-1} 2i−1 + { 0 ∣ 1 } \{0 | 1\} {0∣1} * 2 i − 2 2^{i-2} 2i−2 + … + { 0 ∣ 1 } \{0 | 1\} {0∣1} * 2 1 2^{1} 21 + { 0 ∣ 1 } \{0 | 1\} {0∣1} * 2 0 2^0 20 凑得

for (int i = lg[dep[a]]; i >= 0; i--) {

    if(fa[a][i] != fa[b][i]){
        a = fa[a][i], b = fa[b][i];
    }
}
           

AC Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5e5 + 10;

int e[N << 1], ne[N << 1], h[N], cnt;

void add(int a, int b){
    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}

int n, m, s;
// 用于预处理log(i) 的值
int lg[N];
int dep[N];  // 记录某节点的深度
int fa[N][20];  // 记录某节点的祖先节点; fa[u][0]是父节点

// dfs预处理出来fa数组
void dfs(int u, int pre){

    dep[u] = dep[pre] + 1;
    fa[u][0] = pre;

    for (int i = 1; i <= (lg[dep[u]]); i++) {
        // u的2^i个祖先是u的2^(i-1)个祖先的2^(i-1)个祖先
        // 2^i = 2^(i-1) + 2^(i-1)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if(j == pre) continue;
        dfs(j, u);
    }
}

int lca(int a, int b){
    // 设a的深度较深
    if(dep[a] < dep[b]) swap(a, b);

    // 让a,b到同一深度
    for (int i = lg[dep[a]]; i >= 0; i--) {
        // 利用倍增让a向上走
        // 如果a的2^i个父节点的深度大于等于b,则a向上走
        if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    }
    if(a == b) return a;

    // 找出a和b的lca的直接子节点(即lca下面两个节点)
    for (int i = lg[dep[a]]; i >= 0; i--) {

        if(fa[a][i] != fa[b][i]){
            a = fa[a][i], b = fa[b][i];
        }
    }

    return fa[a][0]; // fa[b][0]
}

int main(){

    memset(h, -1, sizeof h);

    lg[1] = 0;

    for (int i = 0; i < N; ++i) {
        // lg 8 = lg7 + (1 << 3 == 8)
        lg[i] = lg[i-1] + (1 << (lg[i-1] + 1) == i);
    }

    scanf("%d%d%d", &n, &m, &s);

    int x, y;
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }

    dep[s] = 0;
    dfs(s, s);

    int a, b;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
//        printf("%d  %d\n", dep[a], dep[b]);
        printf("%d\n", lca(a, b));
    }

    return 0;
}
           

树上倍增应用题

#include <iostream>
#include <cstring>

using namespace std;

int n, cnt, e[1000], ne[1000], h[1000];
int lg[1000], dep[1000], wd[1000], fa[1000][30];

void add(int a, int b){

    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}

void dfs(int u, int pre){

    dep[u] = dep[pre] + 1;

    fa[u][0] = pre;

    for (int i = 1; i <= lg[dep[u]]; ++i) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }

    for (int i = h[u]; i != -1; i = ne[i]) {

        int j = e[i];
        if(j == pre) continue;
        dfs(j, u);
    }

    wd[dep[u]]++;
}


void lca(int a, int b){

    int x = a, y = b;
    
    // a 为深度深的
    if(dep[a] < dep[b]) swap(a, b);

    // a 上升到和 b 一样高
    for (int i = lg[a]; i >= 0; i--) {

        if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    }

    for (int i = lg[a]; i >= 0; i--) {
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i], b = fa[b][i];
        }
    }

    // lca
    a = fa[a][0];

    cout << (dep[x] - dep[a]) * 2 + (dep[y] - dep[a]) << endl;
}

int main(){

    memset(h, -1, sizeof h);

    lg[1] = 0;
    for (int i = 2; i < 1000; ++i) {
        lg[i] = lg[i - 1] + (1 << (lg[i-1] + 1) == i);
    }

    cin >> n;

    int x, y;

    for (int i = 0; i < n - 1; ++i) {

        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    dfs(1, 1);

    int d = 0, w = 0;

    for (int i = 0; i < 1000; ++i) {
        d = max(d, dep[i]);
        w = max(w, wd[i]);
    }

    cout << d << endl;
    cout << w << endl;

    int u, v;

    cin >> u >> v;

    lca(u, v);

    return 0;
}