LCA

LCA（Lowest Common Ancestor）

向上标记法

对于两个点，从最深的点向上跳，走过的节点进行标记。然后从另一个点向上跳，第一个遇到的就是要求的祖先

时间复杂度 $\Theta(n)$

倍增算法

倍增算法可以分为两个步骤:

1. 调整到同等深度
2. 两个节点在同等深度同时向上找

存图

采用邻接表存图，并记录根节点

预处理深度

采用BFS获得各个点深度，同时根据深度求解fa[i][j]。
fa[i][j]表示第$i$个点向上找深度为$2^j$高度的父节点编号

代码如下

void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    queue<int> q;
    depth[root] = 1;
    depth[0] = 0;
    q.push(root);
    
    while(q.size())
    {
        int node = q.front();
        q.pop();
        for(int i = h[node]; i != -1; i = ne[i])
        {
            int j = e[i];
            
            if(depth[j] > depth[node] + 1)
            {
                depth[j] = depth[node] + 1;
                q.push(j);
                fa[j][0] = node;
                for(int k = 1; k <= 15; k ++)
                {
                    fa[j][k] = fa[fa[j][k-1]][k-1];
                }
            }
        }
        
    }
}

同步倍增

先同步到同一深度，然后向上攀爬

int lca(int a, int b)
{
    if(depth[a] < depth[b]) swap(a, b);
    
    int dep = depth[a] - depth[b];
    
    for(int i = 0; dep > 0; i ++, dep >>= 1)
    {
        if(dep & 1) a = fa[a][i];
    }

    if(a == b) return a;
    
    for(int i = 15; i >= 0; i --)
    {
        if(fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];   
}