莫欺少年穷，修魔之旅在这开始—>算法提高课题解

LCA倍增 + BFS预处理

思路：

1. 先用 bfs 预处理每个点跳 2 ^ k 步后是哪个点，并更新深度
2. 将 depth 更大的点跳到和另一个相同的高度，判断两者是否相等
3. 将两者一起跳到最近公共祖先的下面一层，最后再跳一层跳到最近公共祖先

#include<bits/stdc++.h>

using namespace std;

const int N = 40010, M = 80010;

int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][16];

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

//预处理每个点往上跳 2 ^ k 步后是哪个点
void bfs(int root)
{
    //初始化dist数组
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;

    //初始化队列q
    queue<int> q;
    q.push(root);

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                //更新深度
                depth[j]=depth[t]+1;
                q.push(j);

                //预处理每个点往上跳 2 ^ k 步后是哪个点
                fa[j][0]=t;
                for(int k=1;k<=15;k++) fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    //如果 a 在 b 的上面，就交换位置
    if(depth[a]<depth[b]) swap(a,b);

    //把 a 跳到和 b 一样的高度
    for(int k=15;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];

    //已经跳到最近公共祖先的点了
    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()
{
    cin>>n;

    memset(h,-1,sizeof h);

    int root;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        if(b==-1) root=a;
        add(a,b),add(b,a);
    }

    bfs(root);

    cin>>m;

    while(m--)
    {
        int a,b;
        cin>>a>>b;

        //找到 a 和 b 的最近公共祖先
        int p=lca(a,b);

        // a 是 b 的祖先
        if(p==a) cout<<1<<endl;

        // b 是 a 的祖先
        else if(p==b) cout<<2<<endl;

        // a 和 b 都互不为祖先
        else cout<<0<<endl;
    }

    return 0;
}