***LCA USING BINARY RAIS TREE tutorial

Another easy solution in <O(N logN, O(logN)>
If we need a faster solution for this problem we could use dynamic programming. First, let’s compute a table P[1,N][1,logN] where P[i][j] is the 2^j-th ancestor of i. For computing this value we may use the following recursion:

The preprocessing function should look like this:

  void process3(int N, int T[MAXN], int P[MAXN][LOGMAXN])
  {
      int i, j;
   
  //we initialize every element in P with -1
      for (i = 0; i < N; i++)
          for (j = 0; 1 << j < N; j++)
              P[i][j] = -1;
   
  //the first ancestor of every node i is T[i]
      for (i = 0; i < N; i++)
          P[i][0] = T[i];
   
  //bottom up dynamic programing
      for (j = 1; 1 << j < N; j++)
         for (i = 0; i < N; i++)
             if (P[i][j - 1] != -1)
                 P[i][j] = P[P[i][j - 1]][j - 1];
  }
  

This takes O(N logN) time and space. Now let’s see how we can make queries. Let L[i] be the level of node i in the tree. We must observe that if p and q are on the same level in the tree we can compute LCA(p, q) using a meta-binary search. So, for every power j of 2 (between log(L[p]) and 0, in descending order), if P[p][j] != P[q][j] then we know that LCA(p, q) is on a higher level and we will continue searching for LCA(p = P[p][j], q = P[q][j]). At the end, both p and q will have the same father, so return T[p]. Let’s see what happens if L[p] != L[q]. Assume, without loss of generality, that L[p] < L[q]. We can use the same meta-binary search  for finding the ancestor of p situated on the same level with q, and then we can compute the LCA  as described below. Here is how the query function should look:

  int query(int N, int P[MAXN][LOGMAXN], int T[MAXN], 
  int L[MAXN], int p, int q)
  {
      int tmp, log, i;
   
  //if p is situated on a higher level than q then we swap them
      if (L[p] < L[q])
          tmp = p, p = q, q = tmp;
  
  //we compute the value of [log(L[p)]
      for (log = 1; 1 << log <= L[p]; log++);
      log--;
   
  //we find the ancestor of node p situated on the same level
  //with q using the values in P
      for (i = log; i >= 0; i--)
          if (L[p] - (1 << i) >= L[q])
              p = P[p][i];
   
      if (p == q)
          return p;
   
  //we compute LCA(p, q) using the values in P
      for (i = log; i >= 0; i--)
          if (P[p][i] != -1 && P[p][i] != P[q][i])
              p = P[p][i], q = P[q][i];
   
      return T[p];
  }

Now, we can see that this function makes at most 2 * log(H) operations, where H is the height of the tree. In the worst case H = N, so the overall complexity of this algorithm is <O(N logN), O(logN)>. This solution is easy to code too, and it’s faster than the previous one

-----------------------------------CODE----------------------------------------------------------------------
// tree is treated as 1 based 
// level is also 1 based 

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
list<int>li[1010];
lli dp[1010][30];
int lev[1010];
int dfs(int start,int par,int le)
{

  lev[start]=le;
  list<int>:: iterator it;
  for(it=li[start].begin();it!=li[start].end();it++)
   {
     if(*it!=par)
      {
        dp[*it][0]=start;
        lev[*it]=le+1;
        dfs(*it,start,le+1);
   }
   }
}


int binary_rais(int a,int b)// return lca of a,b
 {
  
    //  always we conseider that lev a> lev b so swap else
   if(lev[a]<lev[b]) swap(a,b);
   
   int lg;
   
   /// maximum jump that can be alloweable to make both a and 
   // b at same level  will be the depth of the node a 
   for(lg=1;(1<<lg)<=lev[a];lg++);
   
   // 
   lg--;
   
   // this will make both at same level
   //  we can write any number as the power of 2 
   //  so by binary raise we can reach to any node 
     for(int i=lg;i>=0;i--)
      {
        if(lev[a]-(1<<i)>=lev[b])
         {
            a=dp[a][i];//   moving a upward
          }
      }
    
    //  now a and b are at same level 
    
    
      //now we always try to  to shift a and be at a point just below the lca
      //  but if both a and b are in the same line than while shifing leven we reach 
      //  both a and become same 
    
   if(a==b) return a;
   
   else
   {
    for(int i=lg;i>=0;i--)
    {
     if(dp[a][i]!=-1 && dp[a][i]!=dp[b][i])//  moving botha and b up 
      {
        a=dp[a][i];
        b=dp[b][i];
      }
    }
    //  since we atmax shift a and b 
    //  just below there lca 
    //  lca will be the parent of a or parent of b
    
    return dp[a][0];
   }
 }


int main()
{

 int t;
  cin>>t;
  int cas=1;
  while(t--)
  {
    cout<<"Case "<<cas++<<":"<<endl;
    for(int i=0;i<1010;i++)li[i].clear();
 int n;
 cin>>n;
 int m ;
  cin>>m;// edge 
  
 for(int i=1;i<=m;i++)
 {
   int a,b;
    cin>>a>>b;
    li[a].push_back(b);
    li[b].push_back(a);
}

 memset(dp,-1,sizeof dp);
 // we are consedering 1 as the root of all nodes 
 // so its parent is non so its pow(2,0) the parent is 0;

 dp[1][0]=0;
 dfs(1,-1,1);

    int max_h=20;//  or lon(n)
    //  maximum height 
    for(int i=1;i<=max_h;i++)
     {
       for(int j=1;j<=n;j++)
        {
            if(dp[j][i-1]!=-1)
       dp[j][i]=dp[dp[j][i-1]][i-1];//
     }
  }
  
  int q;
  cin>>q;
  while(q--)
   {
     int a,b;
      cin>>a>>b;
      cout<< binary_rais(a,b)<<endl;
   }
 }

}