LCA

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

const int N = 100005; // Adjust this based on your maximum number of nodes
const int LOG = 24;    // Enough for trees up to 2^24 nodes

vector<int> g[N];
int table[N][LOG];
int depth[N];

void dfs(int u, int p) {
    table[u][0] = p;
    depth[u] = depth[p] + 1;

    for(int i = 1; i < LOG; i++) {
        table[u][i] = table[table[u][i-1]][i-1];
    }

    for(int v : g[u]) {
        if(v == p) continue;
        dfs(v, u);
    }
}

int find_lca(int u, int v) {
    if(depth[u] > depth[v]) swap(u, v);
    int diff = depth[v] - depth[u];

    // Bring v to the same depth as u
    for(int i = 0; i < LOG; i++) {
        if(diff == 0) break;
        if(diff & (1 << i)) {
            v = table[v][i];
            diff -= (1 << i);
        }
    }

    if(u == v) return u;

    // Now find the LCA
    for(int i = LOG-1; i >= 0; i--) {
        if(table[u][i] != table[v][i]) {
            u = table[u][i];
            v = table[v][i];
        }
    }

    return table[u][0];
}

int main() {
    // Example usage:
    int n; // number of nodes
    cin >> n;

    // Build the tree (n-1 edges)
    for(int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // Initialize
    depth[0] = -1; // Assuming root is 1 and its parent is 0
    dfs(1, 0);     // Start DFS from root (assuming root is 1)

    // Query processing
    int q;
    cin >> q;
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << "LCA of " << u << " and " << v << " is: " << find_lca(u, v) << endl;
    }

    return 0;
}