一种可能较为好写的 LCA O(n) - O(1) 做法

__Cby___ · 2026-10-27 22:38:08 · 算法·理论

:::success[关于AI] 本文经过蓝鲸大哥润色，保证人类区的贡献多于 AI 贡献。 ::: :::success[关于作者] 作者很区，如有错误请在评论区戳我一下/kel :::
听说在 CSP 前写专栏能增加 rp？来实践一下。
或许是 Schieber–Vishkin 算法？但是有一车博客声称这玩意非常难写，不懂了。
先贴代码：

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#define R(a,b,c) for(int a=b;a<=c;a++)
#define E(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
inline int low(int x){return x&-x;}
inline int high(int x){return (1<<(31-__builtin_clz(x)));}
basic_string<int> g[500025];
int ffa[500025];
int dfn[500025];
int top[500025];
int lab[500025];
int asc[500025];
int rnk[500025];
int cnt=0;
int dfs(int u){
    rnk[dfn[u]=++cnt]=u;
    int t=dfn[u];
    for(auto v:g[u]){
        if(v==ffa[u])continue;
        ffa[v]=u;
        dfs(v);
        if(low(lab[v])>low(t))t=lab[v];
    }
    top[lab[u]=t]=ffa[u];
    return 0;
}
inline int enter(int u,int b){
    if(low(lab[u])==b)return u;
    int k=high(asc[u]&~-b);
    return top[(lab[u]&-k)|k];
}
inline int lca(int u,int v){
    if(lab[u]!=lab[v]){
        int k=low(asc[u]&asc[v]&-high(lab[u]^lab[v]));
        u=enter(u,k);
        v=enter(v,k);
    }
    return (dfn[u]<dfn[v]?u:v);
}
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
void print(int x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
int main(){
    int n=rd(),m=rd(),s=rd();
    R(i,1,n-1){
        int u=rd(),v=rd();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(s);
    R(i,1,n){
        int u=rnk[i];
        asc[u]=asc[ffa[u]]|low(lab[u]);
    }
    R(i,1,m)print(lca(rd(),rd())),*O++='\n';
    fwrite(obuf,O-obuf,1,stdout);
    return 0;
}

这份代码在 LCA模板跑了足足 715ms，只能排到最优解第五页，可见其速度并不算非常快，查询常数略大，但是理论复杂度在固定字长的 Word-RAM 模型下，确实是 O(n) - O(1) 的。

变量定义

low(x)：保留 x 的最低二进制位的结果。

high(x)：保留 x 的最高二进制位的结果。

lab[x]：节点 x 子树中使 low(dfn[y]) 最大的那个 y 的 dfn[y]。

asc[x]：把从根到 x 路径上所有节点 y 的 low(lab[y]) 按位或到一个 int 里，即

asc[x]=\bigvee_{y\in path(root,x)} low(lab[y]).

top[l]：所有满足 lab[y]=l 的节点 y 中，深度最小者（簇头）的父亲；若簇头是根，则 top[l]=0。注意下标 l 是 lab 值，不是节点编号，也不是 low(lab) 值。

如何查询

inline int lca(int u,int v){
    if(lab[u]!=lab[v]){
        int k=low(asc[u]&asc[v]&-high(lab[u]^lab[v]));
        u=enter(u,k);
        v=enter(v,k);
    }
    return (dfn[u]<dfn[v]?u:v);
}

如果 lab[u]=lab[v]，则 u,v 在同一条祖先链上（最高点不一定是根），直接用 dfn 判哪个更浅即可。

如果 lab[u]≠lab[v]，需要把 u,v 提到同一条 lab 簇上。为了好写，最终代码降低了可读性，下面放初始代码：

if(lab[u]!=lab[v]){
    int b=high(lab[u]^lab[v]);
    int k=low(asc[u]&asc[v]&~(b-1));
    u=enter(u,k);
    v=enter(v,k);
}

b 是 lab[u] 与 lab[v] 的最高不同位：二者在高于 b 的位上相同，在 b 位不同。

low(lab[x])=b 的节点 x 不一定存在，而 asc 保存了每个节点祖先上实际出现过的 low(lab) 值。因此取公共 asc 中不低于 b 的最低位 k。它对应两条路径分叉前最后共同所在的簇位，也就是 LCA 所在 lab 簇的 low 值。

接下来把 u,v 提升到祖先中满足 low(lab[x])=k 的节点上。初始版本的 enter 如下：

int enter(int u,int b){
    if(low(lab[u])==b)return u;
    int k=high(asc[u]&(b-1));
    int id=(lab[u]&~(k-1))|k;
    return top[id];
}

已经满足条件就返回。注意这里参数 b 是上文的 k，不要混淆。

这里的 k 是 asc[u] 中低于 b 的最高二进制位，即 u 祖先上出现过的低于 b 的最大 low(lab)；它对应的 lab 簇簇头一定在目标节点下面。

id 是把 lab[u] 中低于 k 的二进制位清零，并把值为 k 的那一位置一的结果。此时 id 就是满足 low(lab[x])=k 的那个祖先的 lab；该 lab 簇簇头接在满足 low(lab[x])=b 的祖先下面，所以直接跳到 top[id] 即可。

注意 top 不是簇头，而是簇头的父亲。

如何预处理

挑选你喜欢的预处理方式即可，你可以 dfs 或模拟栈，或者你可以使用 Xor Tree 来实现从下到上递推。

一些关键证明

懒得写了，由蓝鲸大哥完成。~~如果蓝鲸大哥犯唐了评论区戳我一下改用 Astra 大哥。~~ 算了我发现蓝鲸大哥有个别地方写错了，我改天让 gpt 大哥稍微修一下吧，待更新。
:::success[证明] 记：

\ell(x)=lab[x]
\beta(x)=low(\ell(x))
A(x)=asc[x]=\bigvee_{y\in P(x)}\beta(y)
若 \beta(x)=b，称 x 的 \beta 值为 b。注意 b 一定是 2 的幂。
若 \ell(x)=l，称 x 在 lab=l 的簇中。只有固定 lab 值的节点才保证构成祖先链；固定 \beta 值的节点不保证构成链。

一、三个基本结构性质

性质 1：沿根到叶路径，\beta 单调不增

若 y 是 x 的祖先，则

subtree(x)\subseteq subtree(y).

而 \ell(y) 是 subtree(y) 中 lowbit 最大的先序编号，所以

\beta(y)=low(\ell(y))\ge low(\ell(x))=\beta(x).

也就是从根往下走，\beta 只会变小或不变。

性质 2：同一个 `lab` 值的节点形成一条祖先链，且是一段连续路径段

若 \ell(x)=\ell(y)=l，则 l 同时属于 subtree(x) 和 subtree(y)。若 x,y 不可比，则两个子树不交，矛盾。因此它们必在同一条根到叶路径上。

进一步，若 x 是 y 的祖先且二者 lab 相同，中间节点 z 的子树夹在二者之间。由于 l 在

subtree(y)\subseteq subtree(z)\subseteq subtree(x)

中，并且 l 已经是 subtree(x) 中 lowbit 最大的代表，所以 subtree(z) 中 lowbit 最大的代表也只能是 l（同一个 lowbit 值在连续 dfn 区间内唯一）。按 DFS 合并规则，z 的 lab 仍为 l。因此同一个 lab 值的节点确实构成一段连续路径段。

top[l] 在 DFS 后序中被反复赋值，最后写入的是该簇最靠上的节点的父亲，因此

top[l]=\text{簇 }C_l\text{ 最上节点的父亲}.

注意：固定 \beta 值的节点不一定构成链。例如根的一个分支和另一个分支里都可能出现 \beta=2 的节点。

性质 3：`enter(u,b)` 的跳转引理

若 b 是 2 的幂且 b\in A(u)，定义

last_b(u)=\text{路径 }P(u)\text{ 上最深的满足 }\beta(x)=b\text{ 的节点 }x.

则

enter(u,b)=last_b(u).

证明

分两种情况。

情况 1：\beta(u)=b。

此时 u 自己就是路径上最深的 \beta=b 的节点，代码直接返回 u，正确。

情况 2：\beta(u)<b。

因为 b\in A(u)，所以路径上方某个祖先的 \beta=b。由 \beta 单调不增，路径形如

\cdots,\ b,\ \text{若干小于 }b\text{ 的 }\beta\text{ 值},\ \dots,\ \beta(u).

令

x=last_b(u)

为最深的 \beta=b 的祖先。令 y 是 x 到 u 路径上紧挨着 x 下面的儿子。则

\beta(y)<b.

并且从 y 往下直到 u，所有 \beta 都小于 b。因此路径上低于 b 的最高簇位就是

k=high(A(u)\&(b-1))=\beta(y).

也就是说，y 是路径 P(u) 上满足 \beta(y)=k 的最高节点；同时 y 是它所在 lab 簇的簇头。于是

top[\ell(y)]=parent(y)=x.

现在关键是指标

(\ell(u)\&-k)\mid k

为什么等于 \ell(y)。这是 SV 标签的“截断”性质：

由于 y 是 lab 簇簇头，\ell(y) 是该簇中唯一的 lab 值；而 u 在 y 的子树中，\ell(u) 与 \ell(y) 在高于 k 的位上相同，且 \ell(u) 的低 k 位不超过 k。把 \ell(u) 的低位截断到 k，即保留高于 k 的位并令第 k 位为 1、更低位置为 0，正好得到 \ell(y)。可由 DFS 先序区间嵌套直接验证：

(\ell(u)\&-k)\mid k=\ell(y).

因此

enter(u,b) =top[(\ell(u)\&-k)\mid k] =top[\ell(y)] =x =last_b(u).

证毕。

二、LCA 查询为什么正确

记

a=LCA(u,v).

分两种情况。

情况 1：\ell(u)=\ell(v)

由性质 2，同一个 lab 值的节点在同一条祖先链上，因此 u,v 可比。LCA 就是二者中较浅的那个，也就是先序编号较小的那个。代码最后返回

dfn[u]<dfn[v]?u:v

正确。

情况 2：\ell(u)\ne \ell(v)

令

h=high(\ell(u)\oplus \ell(v)),

即两个 lab 的最高不同位。

代码取

k=low(A(u)\&A(v)\&-h).

由于 &-h 会清掉低于 h 的位、保留 h 及以上的位，所以 k 是：

根到 u 与根到 v 的公共路径上出现过的簇位中，不低于 h 的最低者。

注意 A(u)\&A(v) 不一定正好等于公共路径上的簇位集合：固定 \beta 值可以在 a 以下的两个不同分支同时出现。但结合“取不低于 h 的最低位”，最终得到的是 \beta(a)。下面说明这一点。

公共路径 P(a) 上的 \beta 单调不增，最低的公共簇位就是

\beta(a)=low(\ell(a)).

记

b_a=\beta(a).

还需说明 h\le b_a。由于 u,v 都在 subtree(a) 中，而 a 的 lab 的 lowbit 是子树中最大者，subtree(a) 的先序编号落在同一个长度为 2b_a 的块中；任意两个先序编号在高于 b_a 的位上相同。因此 \ell(u) 与 \ell(v) 的最高不同位不会高于 b_a，即

h\le b_a.

于是公共簇位中不低于 h 的最低者正是 b_a，所以

k=b_a=\beta(a).

由 enter 引理：

enter(u,b_a)=last_{b_a}(u),\qquad enter(v,b_a)=last_{b_a}(v).

也就是把 u,v 分别跳到各自路径上最深的 \beta=b_a 的节点。

令

u'=enter(u,b_a),\qquad v'=enter(v,b_a).

因为 a 的 \beta 值就是 b_a，所以 a 本身在 b_a 这一层上。又因为 a 的子树内满足 \beta=b_a 的 dfn 唯一（就是 \ell(a)），所以最多只有一个分支包含 \beta=b_a 的节点：

若某条路径在 a 以下已经离开 \beta=b_a 的层，则它跳到 a；
若某条路径仍在 \beta=b_a 的层中，则它跳到该层内 a 的某个后代。

而 u',v' 都落在同一个 lab 簇中，同一个 lab 簇是一条祖先链，因此最终 LCA 就是 u',v' 中较浅者，也就是先序编号较小者：

dfn[u']<dfn[v']?u':v'.

由于 a 是公共祖先，且最多一个分支包含 \beta=b_a 的节点，所以至少有一条路径会跳到 a。因此这个较浅者正是 a。代码返回