Lowest common ancestor

In a rooted tree, the LCA is the deepest vertex that is an ancestor of both query vertices. Binary lifting answers queries quickly.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Build depth and parent arrays using a tree traversal.
2. Store up[k][v], the ancestor 2^k steps above v.
3. Lift the deeper query vertex to equal depth.
4. Lift both vertices together from large powers to small; their immediate parent is then the LCA.
5. up[k][v] is the 2^k-th ancestor. First equalize depths, then lift both vertices while their candidate ancestors differ. Root self-links make jumps at the root safe.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    int m=n-1;
    vector<vector<int>>g(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // Tree rooted at 1; call build(1,1). LOG chosen for n.
    int LOG=1;
    while((1LL<<LOG)<=n){
        ++LOG;
    }
    vector<vector<int>>up(LOG,vector<int>(n+1));
    vector<int>depth(n+1);
    function<void(int,int)>build=[&](int v,int p){
        up[0][v]=p;
        for(int k=1;k<LOG;++k){
            up[k][v]=up[k-1][up[k-1][v]];
        }
        for(int u:g[v]){
            if(u!=p){
                depth[u]=depth[v]+1;
                build(u,v);
            }
        }
    };
    auto lca=[&](int a,int b){
        if(depth[a]<depth[b]){
            swap(a,b);
        }
        int diff=depth[a]-depth[b];
        for(int k=0;k<LOG;++k){
            if(diff&(1LL<<k)){
                a=up[k][a];
            }
        }
        if(a==b){
            return a;
        }
        for(int k=LOG-1;k>=0;--k){
            if(up[k][a]!=up[k][b]){
                a=up[k][a];
                b=up[k][b];
            }
        }
        return up[0][a];
    };
    build(1,1);
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<'\n';
    }
}

Complexity analysis

O(V log V) preprocessing and space, O(log V) per query.

Example input and output

Read n q, then n−1 undirected tree edges and q query pairs a b. The input must be a valid tree rooted at 1; require 1≤n≤2000 for recursive preprocessing. Print one LCA per query.

Input

5 3
1 2
1 3
3 4
3 5
4 5
2 4
3 3

Output

3
1
3

The deepest shared ancestor of 4 and 5 is 3. Vertices 2 and 4 meet at 1; a vertex is its own ancestor.

Practical applications

Use binary lifting for repeated tree ancestor queries and distance formulas based on depths.

Check your understanding

How do you compute tree distance with LCA x?

Put it into practice

Answer many distance queries on an unweighted tree.