LCA

The lowest common ancestor problem is crucial to solving most tree problems. In a rooted tree, the lowest common ancestor of 2 nodes is the deepest node that is an ancestor of both nodes. 

If the tree is rooted at node 1, then LCA(4, 6) = 2, LCA(5, 3) = 3, and LCA(6, 1) = 1. 

There are many many different ways to find the lowest common ancestor of 2 nodes, however the most popular one is binary lifting. 

The general idea for binary lifting is to precompute a 2D array par, where par[i][j] stores the 2^j th parent of i (0 <= j <= log2(N)). So par[i][0] stores the direct parent, par[i][1] stores the 2nd parent, etc. 

We can precompute that array with a simple DFS as shown later.

Now suppose we receive a query (u, v) and we want to find the LCA of u and v. If u is an ancestor of v or vice versa, then we have already answered the query, so it suffices to first check if u or v is an ancestor of the other. If not, then we should find the highest ancestor of u (closest to root) that is not an ancestor of v. Suppose this node is k, then our LCA is par[k][0]. Clearly this is true since par[k][0] is an ancestor of both u and v and also the first one that is true. 

To check if one node is an ancestor of another, we use the euler tour method. 

struct LCA{
    //LCA with binary lifting
    vector<vector<int>> adj;
    vector<vector<int>> anc;
    int LG;
    int N;
    vector<int> in, out; //euler tour
    int timer = 0;
    LCA(int n){
        LG = ceil(log2(n+1));
        N = n;
        adj.resize(N+1);
        anc.resize(N+1);
        in.resize(N+1);
        out.resize(N+1);
        for(auto &u : anc)u.resize(ceil(log2(n+1)) + 2);
    }
    void ae(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void process(int v = 1, int p = 0){
        anc[v][0] = p; 
        for(int i = 1; i <= LG; i++){
            anc[v][i] = anc[anc[v][i-1]][i-1]; //binary lifting
        }
        in[v] = timer++;
        for(auto u : adj[v]){
            if(u == p)continue;
            process(u, v);
        }
        out[v] = timer;
    }
    //kth ancestor
    //returns -1 is there is no kth parent
    int kth(int v, int k){
        for(int i=0; i <= LG; i++){
            if(k >> i & 1){
                v = anc[v][i];
            }
        }
        return (v == 0 ? – 1 : v);
    }
    bool isAnc(int u, int v){
        return in[u] <= in[v] && out[u] >= out[v];
    }
    int lca(int u, int v){
        if(isAnc(u, v))return u;
        if(isAnc(v, u))return v;
        for(int i = LG; i >= 0; i–){
            if(anc[u][i] != 0 && !isAnc(anc[u][i], v)){
                u = anc[u][i];
            }
        }
        return anc[u][0];
    }
}