LCA|最近公共祖先詳解

cover
查看原文
~~私の Latex😭😭😭~~
はい、今は 2 つの $$ を使う必要があることがわかりました

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)$ の 2 つの異なる部分木に存在します；

$\qquad$ 4. 前順遍歴において、 $LCA(S)$ はすべての $S$ 要素の前に現れ、後順遍歴において $LCA(S)$ はすべての $S$ 要素の後に現れます；

$\qquad$ 5.2 つの点集合の合併の最近公共祖先はそれぞれの点集合の最近公共祖先であり、すなわち
$\qquad LCA(A \cup B) = LCA(LCA(A), LCA(B))$ ;

$\qquad$ 6.2 つの点の最近公共祖先は必ず木の 2 つの点間の最短経路上に存在します；

$\qquad$ 7. $d(u, v) = h(u) + h(v) - 2 \times h(LCA(u, v))$ ここで $d$ は木の 2 つの点間の距離、 $h$ はある点から木の根までの距離 $(dep)$ を表します；

単純な求法#

単純な LCA の求め方は非常にシンプルで、2 つの点が同じになるまで一層一層上に登っていくだけです（ただし、多くの小さな詳細に注意する必要があります）。

$\qquad$ 1. 各点の親ノードと各点の深さ（親ノードまでの距離）を計算します。明らかに、dep [N]、root [N] の 2 つの配列を定義して、 $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 関数を書きます：ここでは 2 つの部分をそれぞれ修正する必要があります。

$\qquad\qquad$ 2.1 $x$ と $y$ の深さを同じにする部分では、いくつかの 2 進数の知識を使用する必要があります。

$\qquad\qquad$ $x$ に対して、 $x$ と $y$ の深さの差に応じて上に登る必要があります。（上に 1 つ登ると、深さが - 1 になります）

$\qquad\qquad$ したがって、 $len$ を $x$ と $y$ の深さの差として記録します。

$\qquad\qquad$ 我々が知るべきことは、 $len$ をどのように 2 の累乗の和に分解するかです（なぜなら st 表は 2 の累乗で保存されているからです）。

$\qquad\qquad$ 例を挙げると

$\qquad\qquad$ $len = 100$ と仮定すると、2 進数に変換すると $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$ の最近公共祖先の前の点であるはずなので、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

ここには何もありません😋