题解 | 最近公共祖先，向上标记法

这题目就是个裸的LCA（最近公共祖先）问题。 向上标记法，就是让两个结点分别检查自己的父节点是否是两者的公共祖先，如果不是，那么大家一起往上跳一层。不断重复这个过程，直到最终收敛到同一个点。（必然收敛，因为最差大家都跳到根节点） 因为这题数据比较弱，是一个完全二叉树，且数值是int范围的，说明最大深度不过30来层，随便跳。 如果题目范围更大，这一步跳的过程，我们是可以用倍增来加速的，如果想要用倍增法加速，那么就需要预处理出每个结点跳$2^{i}2^i$步之后的祖先结点，不过没必要，所以这里略过。

利用完全二叉树的性质，$x\mathrm{/}2x\; /\; 2$就是x的父节点，所以省去构造指针指向父节点的步骤。 然后我们先令两个结点同时跳到同一深度，然后大家再一起往上跳。

#include <iostream>
#include <cmath>

using namespace std;

int main() 
{
    auto get_depth = [&] (int x) -> int { return log2(x); };

    int x, y;
    while (scanf("%d%d", &x, &y) != EOF)
    {
        if (get_depth(x) < get_depth(y))
            swap(x, y);
        
        while (get_depth(x) != get_depth(y))
            x >>= 1;
        while (x != y)
            x >>= 1, y >>= 1;
        printf("%d\n", x);
    }
    return 0;
}