如何求最近公共祖先

1）向上标记法O(nm)
2) 倍增(n + m)logn
做法：先预处理两个数组
depth[i]表示i在树中的深度，dength[1] = 1.
f[i][j] ,表示i这个节点向上跳2^j的祖宗节点编号。可以通过递推算出后面的值。

f[i][0] = 父节点;
for(int k = 1; k <= logn(下取整); k ++)
f[i][k] = f(f[i][k - 1][k - 1]);

可以用dfs或者bfs遍历即可 ，为了防止爆栈一般用bfs.
注意要设置哨兵方便运算。
假如一些点往上2^k跳出了树，那么直接设置f[i][k] = 0;即可。
查找a，b的最近公共祖先步骤：
1）假设a的深度比b大，反之交换即可。利用二进制拼凑的思想找到小于等于depth[b]的a所能跳到的最小值，然后a = f[a][k],直到两者相等为止。

for(int k = logn(下取整); k >= 0; k --)
    if(depth[f[a][k] >= depth[b] )// 哨兵的好处1假如跳出去了，那么depth[a][k] = 0 < depth[b]
    a = f[a][k];

结束之后如果a = b 那么两者已经在同一点上了，返回a或者b即可。
否则的话让两者继续往上跳，一直调到他们的最近公共祖先的下一层。因为如果调到同一层的话我们不知道这个点是不是ab的最近公共祖先

for(int k = log(n)下取整; k >= 0; k --)
    if(f[a][k] != f[b][k])// 哨兵的好处2假如两个点都跳出去，那么f[a][k] = f[b][k] = 0 ，就不会执行。
    {
        a = f[a][k];
        b = f[b][k];
    }

最终答案就是f[a][0] 或者f[b][0];