你可能遇到过这种情况,需要用到 LCA, 但是写一个 ST 表 + RMQ 多了一个欧拉序数组、一个sz变量、一个或两个函数,如果仅仅为 LCA 写树剖就太兴师动众了,这就很不爽。

这时候你需要倍增 LCA。
而倍增 LCA 需要的信息仅仅是 anc[][]dep[]anc[][] 可以替换 fa[] 的位置, dep[] 往往是写不写 LCA 都要维护的常见量。

算法过程很简单, 想学看这里。<-这篇文章过程讲的很好,代码太长太丑。

所以代码也很简单。
我们只多写了一行来维护anc[]
LCA 还是要写一个函数的。

void dfs(int u) {
    for (int i = 1; i < K; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (int e = hed[u]; e; e = nxt[e]) {
        int v = st[e].v;
        if (v == anc[u][0]) continue;
        dep[v] = dep[u] + 1;
    anc[v][0] = u;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int d = dep[u] - dep[v], k = 0; d; d >>= 1, k++) if (d&1) u = anc[u][k]; //达到统一深度
    //下面这个循环必须从大到小。考虑二进制下 1 + 1 = 10
    for (int k = K - 1; k >= 0; k--) if (anc[u][k] != anc[v][k])
        u = anc[u][k], v = anc[v][k];
    return u == v ? anc[u][0];
}