LCA

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 5;
const int M = log2(N) + 1;

int n, l;
vector<int> a[N];

int timer;
int t_in[N], t_out[N];
int up[N][M];

void DFS(int v, int p) {
    t_in[v] = ++timer;
    up[v][0] = p;

    for(int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for(int u : a[v])
        if(u != p) DFS(u, v);
    t_out[v] = ++ timer;
}

bool is_ancestor(int u, int v) {
    return t_in[u] <= t_in[v] && t_out[u] >= t_out[v];
}

int LCA(int u, int v) {
    if(is_ancestor(u, v))
        return u;

    if(is_ancestor(v, u))
        return v;

    for(int i = l; i >= 0; --i)
        if(!is_ancestor(up[u][i], v))
            u = up[u][i];

    return up[u][0];
}

int main() {
    //freopen("LCA.inp", "r", stdin);
    //freopen("LCA.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n-1; ++i){
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    timer = 0;
    l = log2(n);
    DFS(1, 1);

    int t; cin >> t;
    while(t--) {
        int u, v; cin >> u >> v;
        cout << LCA(u, v) << '\n';
    }
    return 0;
}
/*
8
1 2
2 4
4 3
6 3
8 3
5 4
7 4
3
6 4
6 8
8 7

-> 4 3 4
*/