关于图论:最近公共祖先

求最近公共先人的几种办法

1. 向上标记法（暴力做法，不罕用）

工夫复杂度为 O(n)，最坏状况下为一条链；

求 4 和 6 的最近公共先人：首先建设一个 bool 类型的数组用来标记 4 或者 6 的先人，比方，4 的先人是 2,1（从下往上顺次遍历并标记），那就将 2,1 标记为 1，之后标记 6 的先人，在标记过程中如果遇到已被标记的先人，那么这个先人就是 4 和 6 的公共先人，在本例中为 1。

2. 倍增法（罕用）

fa[i,j]示意从 i 开始，向上走 2^j 步所能走到的节点。0<=j<=logn,depth[i]示意深度
步骤：
哨兵：如果从 i 节点跳 2^j 次方步会跳过根节点，那么 fai=0（非凡标记），规定 depth[0]=0;
【1】先将两个点跳到同一层
例如：

如上图，要从 x 节点跳到与 y 节点同一高度
当初已知 depth[x]和 depth[y]
假如 t =depth[x]-depth[y]，为 x 与 y 之间的高度差；
利用二进制拼凑的思维，假如 t =11, 先找到小于等于 11 的最大的 2 的整数幂，也就是 8，那么 11-8=3，接下来再找到小于等于 3 的最大的 2 的整数次幂，也就是 2，那么 3 -2=1，之后再找到小于等于 1 的 2 的整数次幂，也就是 2^0=1，那么 1 -1=0，就拼凑好了 t。
要害局部代码：
//depth 代表节点深度，fai 代表节点 i 向上跳 2^j 步的节点编号

for(int i=15;i>=0;i--)
    {if(depth[fa[u][i]]>=depth[v])
        {u=fa[u][i];
        }
    }

【2】让两个同时往上跳，始终跳到它们的最近公共先人的下一层。
预处理 O(nlogn)
查问 O(logn)

for(int i=15;i>=0;i--)
    {if(fa[u][i]!=fa[v][i])
        {u=fa[u][i];
            v=fa[v][i];
        }
    }