标签：倍增 | 靜海遺跡

Prologue

给定一棵有根树，若节点 $z$ 既是节点 $x$ 的祖先，也是节点 $y$ 的祖先，则称 $z$ 是 $x,y$ 的公共祖先。在 $x,y$ 的所有公共祖先中，深度最大的一个称为 $x,y$ 的最近公共祖先，记为 $\text{LCA} (x,y)$ 。