图论：LCA

LCA: Lowest common ancestor 最近公共祖先

倍增求 LCA

预处理向上跳 $2^k$ 步的结果数组 f[k][x]。

求的时候先把两个点跳到一个深度。这里有一个特判，如果重合直接返回这个点。

然后log值从大往小枚举，两个点一起不断向上跳，直至父亲相同，直接返回父节点。

可以 $O(n)$ 预处理log值，把单次查询复杂度降到 $O(常数)$。

复杂度：预处理 $O(n \log n)$，查询 $O(1)$