LCA

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

int n;
vector<int> adj[400009];
int parent[400009], level[400009], anc[400009][20];

void dfs(int node, int pr, int l)
{
    parent[node] = pr;
    level[node] = l;

    for(auto u : adj[node])
    {
        if(u != parent[node])
            dfs(u, node, l+1);
    }
}

void lca()
{
    dfs(1, -1, 1);

    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; (1 << j) < n; j++)
            anc[i][j] = 1;
    }
    for(i = 0; i < n; i++)
        anc[i][0] = parent[i];

    for(j = 1; 1<<j < n; j++)
    {
        for(i = 0; i < n; i++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
    }
}

int query(int u, int v)
{
    if(level[u] < level[v])
        swap(u, v);

    int i;
    for(i = log2(n) + 1; i >= 0; i--)
    {
        if(level[anc[u][i]] >= level[v])
            u = anc[u][i];
    }

    for(i = log2(n) + 1; i >= 0; i--)
    {
        if(anc[u][i] != anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    }

    return parent[u];
}



int main()
{
    int i, u, v;
    cin >> n;

    for(i = 0; i < n-1; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    lca();

    int q;
    cin >> q;
    while(q--)
    {
        cin >> u >> v;
        cout << query(u, v) << endl;
    }
}
/*
10
1 3
1 7
3 2
3 10
2 6
5 7
8 5
5 9
7 4
2
10 6
2 6
*/