LCA Using Binary Lifting

k=0 means the parent node
Create a table P[K][N] -> N is number of nodes 
2^k<=N 
So k<=logN 
Hence Size of table is N*logN

jumps are made in order of powers of 2 ->1,2,4...etc
trying to divide by 2 

let mid=par[i][k-1] (2^(k-1)th parent if exists)
par[i][k] is par[mid][k-1] 

Its basically dividing a big jump into 2.


First make 2 nodes that we are going to find LCA to same depth using Walk function
if current jump results -1 then we have jumped of the table.

During LCA jump just close to LCA.
Check if jumping makes them equal if not then make the jump.
Do this until ur able to make a jump.

Finally the answer would be an immediate parent of a node.


Preprocessing is O(NlogN) and per query its O(logN)
Space is O(NlogN)
lca-explanation
lca-explanation
lca-explanation
lca-explanation

Do Bfs for depth wrt to any root node

void bfs(vector& adj,vector& par,VII& depth,int& n)
    {
        //arbitrarily root the tree
        VII vis(n,false);
        depth[0]=0;
        vis[0]=true;
        queue q;
        q.push(0);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(auto it:adj[u])
            if(!vis[it])
            {
                vis[it]=true;
                depth[it]=depth[u]+1;
                par[0][it]=u;
                q.push(it);
            }

        }
    }

Preprocess

void preprocess(vector<VII>& par,int& n,int& D)
{
    for(int d=0;d<=D;++d)
    {
        for(int i=0;i<n;++i)
        {

            int mid=par[d-1][i];
            if(mid!=-1)
            par[d][i]=par[d-1][mid];
        }
    }
}

Walk and LCA

int walk(int i,int k,int& D,vector<VII>& par)
{
    //To make a node i at depth d
    for(int d=0;d<=D && i!=-1;++d)
    if((1<<d)&k)i=par[d][i];

    return i;
}
int LCA(int a,int b,vector<VII>& par,VII& depth,int &D)
{
    if(depth[a]>depth[b])
    a=walk(a,depth[a]-depth[b],D,par);
    else if(depth[b]>depth[a])
    b=walk(b,depth[b]-depth[a],D,par);

    if(a==b)
    return a;

    for(int d=D;d>=0;--d)
    {
        //to go close faster make big jumps
        if(par[d][a]!=par[d][b])
        {
            a=par[d][a];
            b=par[d][b];
        }
    }
    return par[0][a];
}


int D=log2(n);