LCA(Least Common Ancestors)最近公共祖先模板（倍增法）

#include<iostream>
#include<vector>
using namespace std;
const int N=4e4+5;
int n,m;
vector<int> g[N];
int d[N],fa[N][20];
void dfs(int u,int f){
    d[u]=d[f]+1,fa[u][0]=f;
    for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i:g[u]) if(i!=f) dfs(i,u); 
}
int lca(int u,int v){
    if(d[u]<d[v]) swap(u,v);
    for(int i=19;i>=0;i--) if(d[fa[u][i]]>=d[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int main(){
    scanf("%d",&n);
    int u;
    for(int i=0;i<n;i++){
        int a,b;scanf("%d %d",&a,&b);
        if(b==-1) u=a;
        else g[a].push_back(b),g[b].push_back(a);
    }
    dfs(u,0);
    scanf("%d",&m);
    while(m--){
        int x,y;scanf("%d %d",&x,&y);
        int t=lca(x,y);
        if(t==x) printf("1\n");
        else if(t==y) printf("2\n");
        else printf("0\n");
    }
    return 0;
}