LCA·倍增

倍增法求 LCA：预处理 up[u][k] 表示 u 向上跳 2^k 步到达的祖先。查询时先把较深的点跳到与另一点同深度，再让两点一起按 2^k 由大到小往上跳，跳到它们的父亲刚好相同为止，那个父亲就是 LCA。单次 O(log n)。