LCA|最近公共祖先详解

cover
查看原文
~~我的 Latex😭😭😭~~
好了，现在知道要套两个 $$ 了

LCA 介紹#

和它的全称一样，lca（ $Lowest Common Ancestor$ ）目的的就是任意两个点最近的公共祖先在哪

性質（或許你不需要記這個）#

From OI-wiki

為了方便，我們記某點集 $S = \left\{ v_1,v_2,...,v_n \right\}$ 的最近公共祖先為 $LCA(v_1,v_2,...,v_n)$ 或 $LCA(S)$

$\qquad$ 1. $LCA(\left\{u\right\}) = u$ ;

$\qquad$ 2. 若 $u$ 是 $v$ 的祖先，當且僅當 $LCA(u, v) = u$ ;

$\qquad$ 3. 如果 $u$ 不為 $v$ 的祖先，並且 $v$ 不為 $u$ 的祖先，那麼 $u, v$ 分別處於 $LCA(u, v)$ 的兩棵不同子樹中；

$\qquad$ 4. 前序遍歷中， $LCA(S)$ 出現在所有 $S$ 元素之前，後序遍歷中 $LCA(S)$ 則出現在所有 $S$ 元素之後；

$\qquad$ 5. 兩點集並的最近公共祖先為兩點集分別的最近公共祖先，即
$\qquad LCA(A \cup B) = LCA(LCA(A), LCA(B))$ ;

$\qquad$ 6. 兩點的最近公共祖先必定處在樹上兩點間的最短路上；

$\qquad$ 7. $d(u, v) = h(u) + h(v) - 2 \times h(LCA(u, v))$ 其中 $d$ 是樹上兩點間的距離， $h$ 代表某點到樹根的距離 $(dep)$ ;

樸素求法#

樸素求 LCA 的想法很簡單，只要一層層往上走直到兩個點相同即可（但是有很多小細節需要注意）。

$\qquad$ 1. 計算每個點的父節點以及每個點的深度（到父節點的距離）顯然，我們需要定義 dep [N], root [N] 兩個數組來分別存儲 $i$ 點的深度和 $i$ 點的父節點，在求 LCA 需要先跑一遍 dfs。

/*
調用函數時，傳入根節點，顯然根節點並沒有父節點，所以_root可以傳入0 形如 init_root(1, 0);
之後在計算dep[N]數組的時候不用特判，直接在dep[0]的基礎上加1，深度就是1（當然你的dep[0]需要初始化）
*/
void init_root(int x, int _root){//x代表當前節點，_root代表當前節點的父節點
    root[x] = _root;//存儲x點的父節點
    dep[x] = dep[_root]+1;//存儲x點的深度
    for(int i = 0; i < mp[x].size(); ++i){//dfs
        int y = mp[x][i];
        if(y == _root)continue;//不能往回走
        init_root(y, x);//下一個點
    }
}

$\qquad$ 2. 接下來就是 LCA 函數了，需要注意的是，對於 $LCA(x, y)$ 其中 $x$ 的深度必須和 $y$ 相同才能一起往上走不然就會～～（愛人～錯過）~，所以在往上走前需要把 $x$ 和 $y$ 的深度弄到相同。

int lca(int x, int y){
    if(dep[x] < dep[y])swap(x, y);//永遠讓dep[x] > dep[y]這樣後面就不用判斷力
    while(dep[x] != dep[y]){
        x = root[x];//讓x 和 y深度相同
    }
    while(x != y){//一起向上走
        x = root[x];
        y = root[y];
    }
    return x;//此時x == y返回誰都行
}

倍增求法#

和樸素的求法不同，倍增求法用 st 表進行預處理，可以減少向上走的次數，從而減少複雜度。

因為需要減少向上走的次數，對於 st [i] [j] 存儲的是從 i 點出發，走了 (1<<j) 個點到的位置。

$\qquad$ 1. 首先我們需要預處理。（dfs 還是要跑的，但是在此處省略，和樸素 LCA 一樣）

void init_st(){
    for(int i = 1; i <= n; ++i){
        st[i][0] = root[i];//st表的初始狀態：i走(1<<0)到的是i的父節點
    }

    for(int j = 1; (1<<j) <= n; ++j){//因為狀態由j-1推到j,所以要先循環j
        for(int i = 1; i <= n; ++i){
            st[i][j] = st[st[i][j-1]][j-1];
            /*
            從i跳（1<<j）個點可以分解成先跳(1<<(j-1))個點，跳到st[i][j-1]，
            再從st[i][j-1]跳(1<<(j-1))個點到st[i][j]
            */
        }
    }
}

$\qquad$ 2. 接下來寫 LCA 函數：這裡需要對兩個部分分別修改。

$\qquad\qquad$ 2.1 對於讓 $x$ 和 $y$ 深度相同的部分，我們需要用到一些 2 進制的知識

$\qquad\qquad$ 對於 $x$ ，需要向上走到步數是 $x$ 和 $y$ 的深度差。（向上走一步，深度 - 1）

$\qquad\qquad$ 所以記錄下 $len$ 為 $x$ 和 $y$ 的深度差。

$\qquad\qquad$ 我們需要知道的是， $len$ 如何分解成 $2$ 的次方相加（因為 st 表是以 2 的次方存儲的）。

$\qquad\qquad$ 舉個栗子

$\qquad\qquad$ 假設 $len = 100$ ，轉成二進制是 $1100100$ ，顯然，

$\qquad\qquad$ 只有對應位是 1 的位置才對總體的值有貢獻，

$\qquad\qquad$ 所以我們當位置存在 $1$ 時，向上走 (1<<i) 個點就行了（i 指對應的位數）

$\qquad\qquad$ 這樣，總共走的點數就會是 $len$ 。

    int len = dep[x]-dep[y];
    int i = 0;//第幾位
    while(len != 0){//使得x, y深度相同 建議腦子裡換成二進制理解
        if(len%2 == 1){//當前位置存在1
            x = st[x][i];//向上走
        }
        len /= 2;//或者右移 (len>>1);
        i++;
    }
    if(x == y)return x;//如果這個時候x == y就說明x和y在同一棵子樹，沒必要進行下一步了。

$\qquad\qquad$ 2.2 接下來需要 $x$ 和 $y$ 一起向上走。

$\qquad\qquad$ 這裡用到二分的思想，但是寫法和常規二分不太一樣。

$\qquad\qquad$ 如果 $x$ 和 $y$ 一起跳了 (1<<i) 個點後，x == y 了，說明跳過了

$\qquad\qquad$ 它們最近的公共祖先深度必然 <= 當前點的深度。

$\qquad\qquad$ 如圖，對於 5 和 4 號點，顯然跳過了它們的最近公共祖先

$\qquad\qquad$ (順手推薦下很方面畫圖的網站https://csacademy.com/app/graph_editor/)

$\qquad\qquad$ 所以顯然，我們需要在第一個 x' != y' 的地方更新 x 和 y 才能保證不走過。

$\qquad\qquad$ (x' 和 y‘指在循環中走跳 (1<<i) 個點時到的點)

$\qquad\qquad$ 這樣得到的點應該是在 $x$ 和 $y$ 的最近公共祖先的前一個點，所以需要返回 root [x]。

//log2(n)函數在頭文件cmath中，得以2為底n的對數
    for(int i = log2(n); i >= 0; --i){
        int _x = st[x][i];//在當前i下x和y跳到的位置
        int _y = st[y][i];
        if(_x == _y)continue;//當x和y跳到的位置相同，說明跳過了，x和y不更新
        x = _x;//更新以二分逼近x和y的最近公共祖先的子節點
        y = _y;
    }
    return root[x];

最後附上包含預處理的完整代碼：

洛谷P3379 【模板】最近公共祖先（LCA）

模板題目也不能抄題解哦ヾ (・ω・`) o

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int N = 1e6;
vector<int> mp[N];
int n, m;
int dep[N], root[N], st[N][20];
/*
調用函數時，傳入根節點，顯然根節點並沒有父節點，所以_root可以傳入0 形如 init_root(1, 0);
之後在計算dep[N]數組的時候不用特判，直接在dep[0]的基礎上加1，深度就是1（當然你的dep[0]需要初始化）
*/
void init_root(int x, int _root){//x代表當前節點，_root代表當前節點的父節點
    root[x] = _root;//存儲x點的父節點
    dep[x] = dep[_root]+1;//存儲x點的深度
    for(int i = 0; i < mp[x].size(); ++i){//dfs
        int y = mp[x][i];
        if(y == _root)continue;//不能往回走
        init_root(y, x);//下一個點
    }
}

void init_st(){
    for(int i = 1; i <= n; ++i){
        st[i][0] = root[i];//st表的初始狀態：i走(1<<0)到的是i的父節點
    }

    for(int j = 1; (1<<j) <= n; ++j){//因為狀態由j-1推到j,所以要先循環j
        for(int i = 1; i <= n; ++i){
            st[i][j] = st[st[i][j-1]][j-1];
            /*
            從i跳（1<<j）個點可以分解成先跳(1<<(j-1))個點，跳到st[i][j-1]，
            再從st[i][j-1]跳(1<<(j-1))個點到st[i][j]
            */
        }
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y])swap(x, y);
    int len = dep[x]-dep[y];//按位取位權
    int i = 0;//第幾位
    while(len != 0){//使得x, y深度相同 建議腦子裡換成二進制理解
        if(len%2 == 1){//當前位置存在1
            x = st[x][i];//向上走
        }
        len /= 2;//或者右移 (len>>1);
        i++;
    }
    if(x == y)return x;//如果這個時候x == y就說明x和y在同一棵子樹，沒必要進行下一步了。
    //log2(n)函數在頭文件cmath中，得以2為底n的對數
    for(int i = log2(n); i >= 0; --i){
        int _x = st[x][i];//在當前i下x和y跳到的位置
        int _y = st[y][i];
        if(_x == _y)continue;//當x和y跳到的位置相同，說明跳過了，x和y不更新
        x = _x;//更新以二分逼近x和y的最近公共祖先的子節點
        y = _y;
    }
    return root[x];
}

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        int x, y;
        cin >> x >> y;
        mp[x].push_back(y);
    }
    init_root(1, 0);
    init_st();
    for(int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
}

例題#

洛谷P9432 [NAPC-#1] rStage5 - Hard Conveyors

這裡什麼都沒有捏😋