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\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 5\n4 6\n3 4

Output:
2\n1\n1

Solution in C++


#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 100005;
int up[MAXN][20], depth[MAXN];
vector<int> 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<<i))
            u = up[u][i];
    }
    if(u == v) return u;
    for(int i=19;i>=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<n;i++){
        int u, v; cin >> 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) << "\n";
    }
    return 0;
}