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;
}