LCA | Recent Common Ancestor Explained

cover
View Original
~~My Latex😭😭😭~~
Okay, now I know to wrap it in two $$.

Introduction to LCA#

As its full name suggests, LCA ( $Lowest Common Ancestor$ ) aims to find the nearest common ancestor of any two points.

Properties (or maybe you don't need to remember this)#

From OI-wiki

For convenience, we denote the nearest common ancestor of a set of points $S = \left\{ v_1,v_2,...,v_n \right\}$ as $LCA(v_1,v_2,...,v_n)$ or $LCA(S)$ .

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

$\qquad$ 2. If $u$ is an ancestor of $v$ , then and only then $LCA(u, v) = u$ ;

$\qquad$ 3. If $u$ is not an ancestor of $v$ and $v$ is not an ancestor of $u$ , then $u$ and $v$ are in two different subtrees of $LCA(u, v)$ ;

$\qquad$ 4. In a preorder traversal, $LCA(S)$ appears before all elements of $S$ , while in a postorder traversal, $LCA(S)$ appears after all elements of $S$ ;

$\qquad$ 5. The nearest common ancestor of the union of two sets is the nearest common ancestor of the two sets, that is,
$\qquad LCA(A \cup B) = LCA(LCA(A), LCA(B))$ ;

$\qquad$ 6. The nearest common ancestor of two points must lie on the shortest path between the two points in the tree ;

$\qquad$ 7. $d(u, v) = h(u) + h(v) - 2 \times h(LCA(u, v))$ where $d$ is the distance between two points in the tree, and $h$ represents the distance from a point to the root of the tree $(dep)$ ;

Naive Method#

The naive idea for calculating LCA is simple: just move up layer by layer until the two points are the same (but there are many small details to pay attention to).

$\qquad$ 1. Calculate the parent of each point and the depth of each point (distance to the parent). Obviously, we need to define two arrays, dep[N] and root[N], to store the depth of point $i$ and the parent of point $i$ , and we need to run a DFS to calculate LCA.

/*
When calling the function, pass in the root node. Obviously, the root node has no parent, so _root can be passed as 0, like init_root(1, 0);
Then, when calculating the dep[N] array, there is no need for special handling; just add 1 based on dep[0], making the depth 1 (of course, your dep[0] needs to be initialized).
*/
void init_root(int x, int _root){//x represents the current node, _root represents the parent of the current node
    root[x] = _root;//store the parent of point x
    dep[x] = dep[_root]+1;//store the depth of point x
    for(int i = 0; i < mp[x].size(); ++i){//dfs
        int y = mp[x][i];
        if(y == _root)continue;//cannot go back
        init_root(y, x);//next point
    }
}

$\qquad$ 2. Next is the LCA function. It is important to note that for $LCA(x, y)$ , the depth of $x$ must be the same as that of $y$ in order to move up together; otherwise, it will~~(lover~missed)~. Therefore, before moving up, we need to make the depths of $x$ and $y$ the same.

int lca(int x, int y){
    if(dep[x] < dep[y])swap(x, y);//always make dep[x] > dep[y] so that we don't need to check later
    while(dep[x] != dep[y]){
        x = root[x];//make x and y have the same depth
    }
    while(x != y){//move up together
        x = root[x];
        y = root[y];
    }
    return x;//at this point x == y, returning either is fine
}

Doubling Method#

Unlike the naive method, the doubling method uses a sparse table for preprocessing, which can reduce the number of upward moves and thus reduce complexity.

To reduce the number of upward moves, the st[i][j] stores the position reached from point i after moving (1<<j) points.

$\qquad$ 1. First, we need to preprocess. (DFS still needs to be run, but it is omitted here, similar to the naive LCA)

void init_st(){
    for(int i = 1; i <= n; ++i){
        st[i][0] = root[i];//initial state of the st table: moving (1<<0) from i reaches the parent of i
    }

    for(int j = 1; (1<<j) <= n; ++j){//because the state is derived from j-1 to j, we need to loop through j first
        for(int i = 1; i <= n; ++i){
            st[i][j] = st[st[i][j-1]][j-1];
            /*
            Jumping (1<<j) from i can be decomposed into first jumping (1<<(j-1)) to reach st[i][j-1],
            then jumping (1<<(j-1)) from st[i][j-1] to st[i][j].
            */
        }
    }
}

$\qquad$ 2. Next, we write the LCA function: here we need to modify two parts separately.

$\qquad\qquad$ 2.1 For making the depths of $x$ and $y$ the same, we need to use some binary knowledge.

$\qquad\qquad$ For $x$ , we need to move up by the number of steps equal to the depth difference between $x$ and $y$ . (Moving up one step decreases depth by 1)

$\qquad\qquad$ So we record $len$ as the depth difference between $x$ and $y$ .

$\qquad\qquad$ What we need to know is how to decompose $len$ into a sum of powers of 2 (since the st table stores powers of 2).

$\qquad\qquad$ For example,

$\qquad\qquad$ Suppose $len = 100$ , converting to binary gives $1100100$ . Clearly,

$\qquad\qquad$ Only the positions where the bit is 1 contribute to the overall value.

$\qquad\qquad$ Therefore, when the position has a 1, we can move up (1<<i) points (where i refers to the corresponding bit position).

$\qquad\qquad$ This way, the total number of points moved will equal $len$ .

    int len = dep[x]-dep[y];
    int i = 0;//which bit
    while(len != 0){//make x and y have the same depth, it is recommended to think in binary
        if(len%2 == 1){//the current position has a 1
            x = st[x][i];//move up
        }
        len /= 2;//or right shift (len>>1);
        i++;
    }
    if(x == y)return x;//if at this point x == y, it means x and y are in the same subtree, no need to proceed to the next step.

$\qquad\qquad$ 2.2 Next, $x$ and $y$ need to move up together.

$\qquad\qquad$ Here we use the idea of binary search, but the writing is slightly different from conventional binary search.

$\qquad\qquad$ If $x$ and $y$ jump (1<<i) points together and become equal, it means they have skipped over their nearest common ancestor.

$\qquad\qquad$ As shown in the diagram, for points 5 and 4, it is clear that they have skipped their nearest common ancestor.

$\qquad\qquad$ (By the way, I recommend a very convenient drawing website https://csacademy.com/app/graph_editor/)

$\qquad\qquad$ Therefore, we need to update $x$ and $y$ at the first point where $x' \neq y'$ to ensure we do not skip over.

$\qquad\qquad$ ( $x'$ and $y'$ refer to the points reached when jumping (1<<i) points in the loop)

$\qquad\qquad$ Thus, the point obtained should be the point before the nearest common ancestor of $x$ and $y$ , so we need to return root[x].

// The log2(n) function is in the cmath header, which gives the logarithm of n to the base 2.
    for(int i = log2(n); i >= 0; --i){
        int _x = st[x][i];//the position reached by x and y at the current i
        int _y = st[y][i];
        if(_x == _y)continue;//if the positions reached by x and y are the same, it means they have skipped, do not update x and y
        x = _x;//update to approach the nearest common ancestor of x and y
        y = _y;
    }
    return root[x];

Finally, here is the complete code with preprocessing:

Luogu P3379 【Template】Lowest Common Ancestor (LCA)

You can't just copy the solution for template problems ヾ (・ω・`) 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];
/*
When calling the function, pass in the root node. Obviously, the root node has no parent, so _root can be passed as 0, like init_root(1, 0);
Then, when calculating the dep[N] array, there is no need for special handling; just add 1 based on dep[0], making the depth 1 (of course, your dep[0] needs to be initialized).
*/
void init_root(int x, int _root){//x represents the current node, _root represents the parent of the current node
    root[x] = _root;//store the parent of point x
    dep[x] = dep[_root]+1;//store the depth of point x
    for(int i = 0; i < mp[x].size(); ++i){//dfs
        int y = mp[x][i];
        if(y == _root)continue;//cannot go back
        init_root(y, x);//next point
    }
}

void init_st(){
    for(int i = 1; i <= n; ++i){
        st[i][0] = root[i];//initial state of the st table: moving (1<<0) from i reaches the parent of i
    }

    for(int j = 1; (1<<j) <= n; ++j){//because the state is derived from j-1 to j, we need to loop through j first
        for(int i = 1; i <= n; ++i){
            st[i][j] = st[st[i][j-1]][j-1];
            /*
            Jumping (1<<j) from i can be decomposed into first jumping (1<<(j-1)) to reach st[i][j-1],
            then jumping (1<<(j-1)) from st[i][j-1] to st[i][j].
            */
        }
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y])swap(x, y);
    int len = dep[x]-dep[y];//bitwise take the weight
    int i = 0;//which bit
    while(len != 0){//make x and y have the same depth, it is recommended to think in binary
        if(len%2 == 1){//the current position has a 1
            x = st[x][i];//move up
        }
        len /= 2;//or right shift (len>>1);
        i++;
    }
    if(x == y)return x;//if at this point x == y, it means x and y are in the same subtree, no need to proceed to the next step.
    // The log2(n) function is in the cmath header, which gives the logarithm of n to the base 2.
    for(int i = log2(n); i >= 0; --i){
        int _x = st[x][i];//the position reached by x and y at the current i
        int _y = st[y][i];
        if(_x == _y)continue;//if the positions reached by x and y are the same, it means they have skipped, do not update x and y
        x = _x;//update to approach the nearest common ancestor of x and 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;
}

Example Problems#

Luogu P9432 [NAPC-#1] rStage5 - Hard Conveyors

There is nothing here😋