# data[].attributes.attachment_link.readable_text
#include <bits/stdc++.h>
using namespace std;
int n,q;
int p[100005][17], depth[100005];
vector <int> G[100005];

FILE *fi=freopen("1.txt","r",stdin);

int lca(int x,int y){
    //Cho thằng x làm thằng sâu hơn
    if (depth[x] < depth[y])
        swap(x, y);

    //Cho 2 nút về cùng độ cao
    for(int k=16;k>=0;k--)
        if (depth[p[x][k]] >= depth[y])
            x = p[x][k];

    //Kiểm tra xem 2 thằng có giống nhau không
    if (x == y)
        return x;

    //Cho 2 thằng về tiền tố nằm ngay dưới tổ tiên chung gần nhất
    for(int k=16;k>=0;k--)
        if (p[x][k] != p[y][k])
            x = p[x][k],
            y = p[y][k];

    return p[x][0];
}

int dfs(int u,int parent){
    p[u][0] = parent;

    //Tính mảng p trong khi dfs
    for(int k = 1; k < 17; k ++)
        p[u][k] = p[p[u][k-1]][k-1];

    for(auto v: G[u]){
        if (v == parent)    continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int main(){
    std::ios_base::sync_with_stdio(0);

    std::cin >> n;

    for(int i=1;i<n;i++){
        int x, y;
        std::cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    depth[1] = 1;
    dfs(1, 0);

    int q;
    std::cin >> q;

    while(q--){
        int a, b;
        std::cin >> a >> b;
        std::cout << lca(a, b) << '\n';
    }
}

# data[].attributes.body
Gọi p[i][j] là gốc cha thứ 2^j của nút i
Trong vd dưới :
p[3][1]=6

# data[].attributes.body
Hình minh họa