Problem 50: Lowest Common Ancestor in Tree using Binary Lifting

Problem Statement: Given a tree with n nodes (1-indexed) and q queries, preprocess the tree using binary lifting so that you can answer LCA queries in O(log n) time. For each query, given two nodes, output their lowest common ancestor.

Input

The first line contains an integer n. The next n-1 lines contain two integers u and v representing an edge of the tree. The next line contains an integer q, followed by q lines each containing two integers u and v representing a query.

Output

For each query, print the lowest common ancestor of the two nodes.

Examples


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

Output:
2
1
3

Solution Explanation

Method 1: Preprocess the tree using DFS to compute depths and build a binary lifting table. Answer each LCA query by equalizing depths and then simultaneously lifting both nodes until they meet. Method 2: Use an Euler tour to reduce the LCA query to a Range Minimum Query (RMQ), which can be solved efficiently using a segment tree.

Solution in C++


#include 
#include 
#include 
using namespace std;

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

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

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    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);
    
    int q; cin >> q;
    while(q--){
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "
";
    }
    return 0;
}