CODECHEF-TALCA , BINARY LIFTING LCA

/*
In a rooted tree, the (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.


Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.

Input

The first line contains a single integer N. Each line in the next N - 1 lines contains a pair of integer u and v representing a edge between this two vertices.
The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers r, u, v representing a query.

Output
For each query, write out the answer on a single line.

Constraints

1 ≤ N, Q ≤ 2 × 10^5


Example
Input:
4
1 2
2 3
1 4
2
1 4 2
2 4 2

Output:
1
2

Explanation
"1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
"2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.
*/

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> dp(200001,vector<int>(20,-1));
vector<int> level(200001,0);
vector<int> parent(200001,0);
vector<int> adj[200001];


void DFS(int node, int depth, int par){
    level[node]=depth;
    parent[node]=par;
    for(auto nei: adj[node]){
        if(nei!=par){
            DFS(nei,depth+1,node);
        }
    }
}

void precomputation(int n){
    for(int node=1;node<=n;node++){
        dp[node][0]=parent[node];
    }
    for(int node=1;node<=n;node++){
        for(int jump=1;jump<20;jump++){
            if(dp[node][jump-1]!=-1){
                dp[node][jump]=dp[dp[node][jump-1]][jump-1];
            }
        }
    }
}

void moveUP(int &u, int v){
    int k=level[u]-level[v];
    for(int i=19;i>=0;i--){
        if(k>=pow(2,i)){
            k-=pow(2,i);
            u=dp[u][i];
        }
    }
}

int LCA(int node1, int node2){
    if(level[node1]>level[node2]){
        moveUP(node1,node2);
    }
    if(level[node1]<level[node2]){
        moveUP(node2,node1);
    }
    if(node1==node2){
        return node1;
    }
    for(int jump=19;jump>=0;jump--){
        if(dp[node1][jump]!=dp[node2][jump]){
            node1=dp[node1][jump];
            node2=dp[node2][jump];
        }
    }
    return dp[node1][0];
}


void solve(){
    int N;
    cin>>N;
    for(int i=0;i<N-1;i++){
        int node1,node2;
        cin>>node1>>node2;
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }
    DFS(1,0,0);
    precomputation(N);
    int q;
    cin>>q;
    while(q--){
        int r,u,v;
        cin>>r>>u>>v;

        int a=LCA(u,v);
                int b=LCA(r,u);
                int c=LCA(r,v);

                if(a==b) cout<<c<<endl;
                else if(b==c) cout<<a<<endl;
            else if(a==c) cout<<b<<endl;
    }
}

int main(){
    solve();
    return 0;
}