倍增LCA

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

const int N=40005;
const int M=2*N;

int head[N], depth[N], fa[N][16]; // 2^16-1=65535>40000 可以覆盖所有点
int n, m, E=0;

struct Edge{
    int v, ne;
}e[M];

inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

void bfs(int root){
    memset(depth, 0x3f, sizeof depth);
    depth[0]=0; // 设置哨兵节点
    depth[root]=1; // 根节点的深度为1
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int node=q.front(); q.pop();
        for(int i=head[node]; ~i; i=e[i].ne){
            int v=e[i].v;
            if(depth[v]>depth[node]+1){
                depth[v]=depth[node]+1;
                q.push(v);
                fa[v][0]=node;
                for(int k=1; k<=15; ++k){
                    fa[v][k]=fa[fa[v][k-1]][k-1];
                }
            }
        }
    }
}

int lca(int x, int y){
    if(depth[x]<depth[y]) swap(x, y);
    for(int k=15; k>=0; --k)
        if(depth[fa[x][k]] >= depth[y])
            x=fa[x][k];
    if(x==y) return x;
    for(int k=15; k>=0; --k){
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}

int main(){
    cin>>n;
    int root=0;
    // 预处理
    memset(head, -1, sizeof head);
    for(int i=0; i<n; ++i){
        int a, b;
        cin>>a>>b;
        if(b==-1) root=a; // 记录根节点的位置
        else add(a, b), add(b, a); //建立双向边
    }

    bfs(root);
    // 查询
    cin>>m;
    while(m--){
        int x, y;
        cin>>x>>y;
        int pa=lca(x, y);
        if(pa==x) cout<<"1"<<endl;
        else if(pa==y) cout<<"2"<<endl;
        else cout<<"0"<<endl;
    }

    return 0;
}