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 in C++


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

const int MAXN = 100005;
int up[20][MAXN];
int depth[MAXN];
vector<int> 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) << "\n";
    }
    return 0;
}

Prev
Home