LCA (Longest Common Anchestor)

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
int level[100005], parnt[100005];
vector<int>vec[100005];
int n;
void dfs(int u,int par,int depth)
{
    level[u]=depth;
    parnt[u]=par;
    for(int i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if(v!=par)
        {
            dfs(v,u,depth+1);
        }
        else
            continue;
    }
}
int dist[100005][20];
void lca_init()
{
    memset(dist,-1,sizeof(dist));
    for(int i=0; i<n; i++)
    {
        dist[i][0]=parnt[i];
    }
    for(j=1;j<20;j++)
    {
        for(i=1;i<=n;i++)
        {
            if(dist[i][j-1]!=-1)
                dist[i][j]=dist[dist[i][j-1]][j-1];
        }
    }
}
int lca(int x,int y)
{
    if(level[x]<level[y])
        swap(x,y);
    int power=1;
    while(1)
    {
        if(1<<(power+1)>level[x])
        {
            break;
        }
        power++;
    }
/// int power= log2(level[u]); eitao kora jai
    for(int i=power;i>=0;i--)
    {
        if(level[x]-(1<<i)>=level[y])
        {
            x=dist[x][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=power;i>=0;i--)
    {
        if(dist[x][i]!=-1&&dist[x][i]!=dist[y][i])
        {
            x=dist[x][i],y=dist[y][i];
        }
    }
    return parnt[x];
}
main()
{
    cin>>n;
    int u,v,i;
    for(i=1; i<n; i++)
    {
        cin>>u>>v;
        u--,v--;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(0,0,0);
    lca_init();
    int q;
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>u>>v;
        u--,v--;
        cout<<lca(u,v)+1<<endl;
    }
}


/*
9    ///node no
1 2
1 3
2 4
2 5
5 7
5 8
8 9
3 6
5     ///query
7 9   /// lca of 7 9 is 5
7 8   /// lca of 7 8 is 5
4 7   /// lca of 4 7 is 2
4 8   /// lca of 4 8 is 2
9 6   /// lca of 9 6 is 1

Ouptut:
5
5
2
2
1

*/