LCA

例题
给定一颗多叉树，求两个点的最近公共祖先

dfs遍历预处理出每个节点的父亲信息，存在fa[x][0]中。
fa[x][j]为x点向上走2^i步所到的节点
depth[x]为x点所在的深度

void dfs(int x,int f)
{
    v[x] = 1;
    dpth[x] = dpth[f] + 1;
    fa[x][0] = f;
    for (int i = 1; i <= t;i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = head[x]; i;i=net[i])
    {
        int v1 = ver[i];
        if(v[v1])
            continue;
        dfs(v1, x);
    }
}

每个点向上走任意步数能到达的点都能通过倍增数组表示出来。
1、利用2进制拆分思想，向上调整深度大的点y,直到和点x深度相同
l 从大到小枚举k，比较x和fa[y][k]，一直调整到和x深度相同f=f[y][k]。
2、调整到同一深度后：此刻x和fa[y][k ]相等，说明x为LCA
否则说明两个点还没走过LCA，两个点同时
向上往深度大于LCA的点跳
跳到最后会停留在LCA下面
3、最后再向上跳一步就是LCA
代码

int lca(int x,int y)
{
    if(dpth[x]>dpth[y])
        swap(x, y);
    for (int i = t; i >= 0;i--)
        if(dpth[fa[y][i]]>=dpth[x])
            y = fa[y][i];
    if(x==y)
        return x;
    for (int i = t; i >= 0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}