代码解释

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=40010,M=2*N;
int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][16];  //fa的含义见36行
int q[N];

void add(int a,int b)//建表
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);   //初始化深度
    depth[0]=0,depth[root]=1;   //初始化根节点的深度为1
    int hh=0,tt=0;//定义表头、表尾
    q[0]=root;//将根节点加入队列
    while(hh<=tt)  //循环整个队列
    {
        int t=q[hh++];//取出队头
        for(int i=h[t];~i;i=ne[i])//遍历
        {
            int j=e[i];//取出节点
            if(depth[j]>depth[t]+1)//如果当前的深度大于上一个节点的深度+1
            {
                depth[j]=depth[t]+1;//更新当前节点的深度
                q[++tt]=j;//加入队列
                fa[j][0]=t;   //表示节点j走2的0次方步，也就是节点j走1步的节点为t。
                for(int k=1;k<=15;k++)
                  fa[j][k]=fa[fa[j][k-1]][k-1];   
                  //根据fa[j][0]，不难看出fa[j][k]这个公式的含义为：
                  //节点j跳2的k-1次方到达的节点，之后以这个节点再跳2的k-1次方。
                  //注意：这里的2的k-1次方，均为一个节点到另一个节点所需要的步数。
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);//调整a和b的深度

    for(int k=15;k>=0;k--)//采用二进制来对a节点进行更新
       if(depth[fa[a][k]]>=depth[b])//如果节点a跳之后的节点的深度大于等于b节点的深度
       a=fa[a][k];//更新a这个节点，并到达当前的节点。

    if(a==b)   return a;//第一种情况，当a节点跳之后的节点恰好相等b节点，直接返回
    for(int k=15;k>=0;k--)//第二种情况，跳起飞了哈哈哈。
       if(fa[a][k]!=fa[b][k])  //不超过根节点
       {
           a=fa[a][k];
           b=fa[b][k];
       }
    return fa[a][0];
}

int main()
{
    scanf("%d",&n);
    int root=0;//定义根节点
    memset(h,-1,sizeof h);//初始化邻接表
    for(int i=0;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b==-1)   root=a;
        else add(a,b),add(b,a);//无向图
    }
    bfs(root);//相当于预处理
    scanf("%d",&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int p=lca(a,b);
        if(p==a)  puts("1");
        else if(p==b)  puts("2");
        else puts("0");
    }
    return 0;
}