浅谈LCA

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

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];//  depth 深度 作用是计算两个点的深度差值 
                       //  fa[i][j]  代表 从j 开始2 ^ j个点的父节点 主要目的记录路径
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; //哨兵
    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)
            {
                depth[j] = depth[t] + 1;
                q[++ tt] = j;
                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) // lca返回 a b 的祖宗节点
{
    if(depth[a] < depth[b]) swap(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;
    for(int k = 15; k >= 0; k --) //a b向上跳跃
       if(fa[a][k] != fa[b][k]) //只要父节点不相同就一直上跳
       {
           a = fa[a][k];
           b = fa[b][k];
       }
    return fa[a][0];   
}

int  main()
{
    cin >> n;
    int root = 0;
    memset(h, -1, sizeof h);

    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 a, b;
        cin >> a >> b;



         int p = lca(a, b);
        if(p == a)puts("1");
        else if(p == b) puts("2");
        else puts("0");
    }
    return 0;



}