倍增 LCA

一句话理解

倍增 LCA：对齐深度后一起跳到 LCA 下方。

为什么要学

O(log n) 查询，O(n log n) 预处理。

讲解

若 fa[k][u]!=fa[k][v] 则都跳。最后父亲就是 LCA。

例子

两个点同时往上，直到再跳一步就会相遇。

常见错误

• 一个是另一个祖先的情况没先处理。
• LOG 从 0 到最大写反。