1. 树上倍增——倍增求 LCA
LCA 指的是最近的公共祖先，倍增法求解 LCA 的步骤如下。
（1）预处理
a. 求深度：对于每个节点 dfs 预处理处节点深度；
b. 求倍增祖先：计算出每个节点向父元素跳 步所到达的节点（在这里
大于整棵树的最大深度）
备注：
a. 设 f [ x , k ] 表示节点 x 向上跳 步能到达的祖先， f [ x , 0 ] 表示 x 的父元素，如对应节点不存在 f [ x , k ] = 0。
b. 将路径长度 分为两半，x 跳
次到的祖先 = x 跳
次到的祖先再跳
次。
因此可得： f [ x , k ] = f [ f [ x ] [ k-1 ] , k-1 ]。
c. 有 n 个节点，每个节点能向上跳的最大次数为 ，因此预处理的时间复杂度为
。
（2）查询
对于多次查询节点 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；
备注：单词查询的时间复杂度为 。