1
2
3
4
5
6
7
8
9
10
11
int fa[N],st[N][20],dep[N];
void dfs(int u,int f,int d){
    fa[u]=f;dep[u]=d;st[u][0]=f;
    for(int i=1;i<=19;i++){
        st[u][i]=st[st[u][i-1]][i-1];
    }
    for(auto v:G[u]){
        if(v==f||v==u) continue;
        dfs(v,u,d+1);
    }
}

以上为 dfs 函数。dfs 函数的意义是预处理每个点 $N$ 向上跳跃 $2^i (0 \leq i \leq 19)$ 个节点的结果。

1
2
3
4
5
6
7
8
9
10
11
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int k=19;k>=0;k--){
        if(dep[ st[x][k] ]>=dep[y]) x=st[x][k];
    } 
    if(x==y) return x; 
    for(int k=19;k>=0;k--){
        if(st[x][k]!=st[y][k]) x=st[x][k],y=st[y][k]; 
    }
    return st[x][0];
}

以上为 lca 函数。lca 函数的处理分为 2 步：

  1. 保证 $dep_x \leq dep_y$ ，并向上跳跃直至 $dep_x = dep_y$ 。不妨令 $x$ 低于 $y$ ，即 $x$ 需要向上跳到与 $y$ 高度相同的节点，即若 $dep_{node(x,2^k)} \geq dep_y$ 则跳跃。当处理完毕后若 $x$ 与 $y$ 为同一节点，则返回 $x$ 。

  2. 向上寻找，迫近 $LCA(x ,y)$ 的直接儿子节点。若 $node(x,2^k)$ 与 $node(y,2^k)$ 不同，就说明 $x$ 与 $y$ 还在 $LCA(x ,y)$ 以下，则跳跃。最终返回 $node(x,2^0)$ 或 $node(y,2^0)$ ，事实上这两个点就是同一个节点。

今天是 CSP-J2/S2 的前夕。写下这篇笔记的原因是确保明天我还看得懂我写的是什么。

2024/10/25，@co7ahang 于 SSDF 三机房。