倍增求 LCA

1. 树上倍增——倍增求 LCA

LCA 指的是最近的公共祖先，倍增法求解 LCA 的步骤如下。

a. 求深度：对于每个节点 dfs 预处理处节点深度；

b. 求倍增祖先：计算出每个节点向父元素跳 $2^{0},2^{1},2^{2},...,2^{k}$ 步所到达的节点（在这里 $2^{k}$ 大于整棵树的最大深度）

备注：

a. 设 f [ x , k ] 表示节点 x 向上跳 $2^{k}$ 步能到达的祖先， f [ x , 0 ] 表示 x 的父元素，如对应节点不存在 f [ x , k ] = 0。

b. 将路径长度 $2^{k}$ 分为两半，x 跳 $2^{k}$ 次到的祖先 = x 跳 $2^{k-1}$ 次到的祖先再跳 $2^{k-1}$ 次。

因此可得： f [ x , k ] = f [ f [ x ] [ k-1 ] , k-1 ]。

c. 有 n 个节点，每个节点能向上跳的最大次数为 $log_{N}$ ，因此预处理的时间复杂度为 $n*log_{n}$ 。

对于多次查询节点 x 和 y 的公共祖先：

a. 如果 x 的深度 < y 的深度，则交换 x y，使得 x 更深；

b. 采用二进制拆分的思想，根据两个节点的深度差，让 x 快速跳转到和 y 一样深；

c. 如果此时 x==y，可得 LCA；

d. 如果不相等，采用二进制拆分的思想，让 x y 倍增上跳，直到 x 的父相遇（因为跳出根以上， f [ x ] [ y ] = 0，因此如果让 x 和 y 相遇，可能结果为 0 ），可得 LCA；