问题背景：求两点最近公共祖先

解法1. 标记法：从其中一点a开始向树根遍历，经过的点（包括节点a本身）全部打上标记，结束之后从b开始向上遍历，遇到第一个被标记的点就是答案。

解法2：倍增
解法2是对解法1的一种优化，我们维护两个数组depth表示节点深度 depth[root] = 1, depth[0] = 0, fa[j][k]表示从j向上走2^k步走到的节点。
如何初始化两个数组呢？
宽搜，depth[j] = depth[t] + 1, fa[j][k] = fa[fa[j][k-1]][k-1]

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> q;
    q.push(root);

    int i = 0;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();

        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.push(j);
                fa[j][0] = t;
                for(int k = 1; k <= 20; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

如何求答案呢？
我们让两个节点到同一层，在下边的移动到和上边节点同一高度，若发现 a == b, 则证明 b 是 a 的祖先
若 a ≠ b，则让 a 和 b同时上升
操作：
和解法1不同的是我们可以借助已经初始化好的depth和fa来快速移动，假设depth[a] - depth[b] = 15, a = fa[a][k] 的先决条件是 depth[fa[a][k]] >= depth[b]

int lca(int a, int b)
{
    //让下边的找上边的
    if(depth[a] < depth[b]) swap(a, b);
    for(int k = 20; k >= 0; k--)
        if(depth[fa[a][k]] >= depth[b]) 
            a = fa[a][k];

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