Problem 12: Lowest Common Ancestor (Binary Lifting)

Problem Statement: Given a tree and multiple queries, determine the lowest common ancestor (LCA) of two nodes using binary lifting technique.

Input

The first line contains n and q. Next n-1 lines contain two integers u and v representing an edge. Then q lines follow, each containing two nodes for which LCA is required.

Output

For each query, print the LCA of the given nodes.

Examples


Input:
7 3
1 2
1 3
2 4
2 5
3 6
3 7
4 5
4 6
3 4

Output:
2
1
1

Solution Explanation

Method 1: Preprocess the tree using DFS to compute depths and build a binary lifting table. Then answer each query by equalizing the depth and moving both nodes up until the LCA is found. Method 2: Use Euler Tour + RMQ technique where the LCA query reduces to a range minimum query over the Euler tour array.

Solution in C++


#include 
#include 
#include 
using namespace std;

const int MAXN = 100005;
int up[MAXN][20], depth[MAXN];
vector adj[MAXN];

void dfs(int u, int p){
    up[u][0] = p;
    for(int i=1; i<20; i++){
        if(up[u][i-1] != -1)
            up[u][i] = up[up[u][i-1]][i-1];
        else 
            up[u][i] = -1;
    }
    for(auto v : adj[u]){
        if(v != p){
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for(int i=0;i<20;i++){
        if(d & (1<=0;i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int main(){
    int n, q;
    cin >> n >> q;
    for(int i=1;i<=n;i++) adj[i].clear();
    for(int i=1;i> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    depth[1] = 0;
    dfs(1, -1);
    while(q--) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "
";
    }
    return 0;
}