********************************************

这题是公共祖先模板题。

我们用倍增方法去写。

首先我们找到根节点，然后从当前根节点往下dfs

在dfs的过程中我们遍历的节点初始上一步的节点f[u][0] = father

然后再初始化后几步的节点。

for(int i = 1;i<=20;++i){   //往上跳2^i步的节点 
    f[u][i] = f[f[u][i-1]][i-1];
}

这样我们倍增出了关于当前节点的倍增父节点。

然后我们遍历子节点，更新其深度，方便后面找公共祖先时平衡两节点的深度在同一个位置上。

for(int i:arr[u]){
   if(i==father)continue;
   dep[i] = dep[u] + 1;    //往下更新下节点的深度
        
   dfs(i,u);
}

到后面的查询操作：

我们一开始先平衡两节点的深度到达同一个位置。

然后开始往上慢慢找第一个深度最大的不同节点， 就能找到公共最近节点了。

ac code:

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

const int N = 4e4+5;

vector<int>arr[N];

int root;

int dep[N];     //节点深度
int f[N][26];   //往上跳2^i步的父节点

void dfs(int u,int father){     //更新节点深度和跳一步的父节点
    
    if(father==-1)f[u][0]=u;    //如果当前节点是根
    else f[u][0] = father;      //不是根就指向上一级节点
    
    for(int i = 1;i<=20;++i){   //往上跳2^i步的父节点 
        f[u][i] = f[f[u][i-1]][i-1];
    }
    
    for(int i:arr[u]){
        if(i==father)continue;
        dep[i] = dep[u] + 1;    //往下更新下节点的深度
        
        dfs(i,u);
    }
}

int LCA(int a,int b){
    int op = 1; //没交换
    if(dep[a]<dep[b]){  //将深度大的变a
        swap(a,b);
        op = 2; //交换状态
    }
    
    while(dep[a]>dep[b]){
        for(int i = 20;i>=0;--i){   //贪心跳最大
            if(dep[f[a][i]]>=dep[b]){   //如果跳了深度大于等于b就跳
                a = f[a][i];
                break;
            }
        }
    }    
    
    if(a==b){   //如果a往上跳等于b，说明其中一方是另一方的公共祖先
        if(op==1)return 2;   //没交换时，y是x的公共祖先
        else return 1;  //x是y的公共祖先
    }
    
    return 0;
    
}

void solve(){
    int n;cin>>n;
    
    for(int i = 1;i<=n;++i){
        int a,b;cin>>a>>b;
        // cout<<i<<' '<<a<<' '<<b<<endl;
        if(a==-1){root = b;continue;}
        if(b==-1){root = a;continue;}
        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    dfs(root,-1);
    int k;cin>>k;
    
    while(k--){
        int a,b;cin>>a>>b;
        int res = LCA(a,b);
        cout<<res<<endl;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}