倍增法求LCA

vector<int> e[500010];
int dep[500010],fa[500010][20];

void solve(){
    cin>>n>>m>>s;
    for (int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(s,0);
    while (m--){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
}

定义 $Fa_{i,j}$ 表示 $i$ 节点向上跳 $2^j$ 层的祖先节点，可以由递推式得来

$$ Fa_{i,j}=Fa_{Fa_{i,j-1},{j-1}} $$

首先DFS遍历树，每次记录节点的深度以及该节点的父节点，即 $Fa_{x,0}=p$

void dfs(int x,int p){
    dep=dep[p]+1;//当前节点深度为父节点深度+1
    fa[0]=p;
    for (int i=1;i<=19;i++)//倍增法递推
        fa[i]=fa[fa[i-1]][i-1];
    for (auto v:e){//DFS叶子节点
        if (v==p) continue;
        dfs(v,x);
    }
}

利用 $Fa_{i,j}$ 计算 LCA

首先需要将节点 $x,y$ 跳到同一层，然后两个节点一起向上跳到最近公共祖先的下一层

int lca(int x,int y){
    if (dep<dep[y]) swap(x,y);//保证x的深度较大
    for (int i=19;i>=0;i--){
        if (dep[fa[i]]>=dep[y])//将深节点x跳到y节点同一层上
            x=fa[i];
    }
    if (x==y) return y;//如果y是x的祖先节点，那么直接返回
    for (int i=19;i>=0;i--){
        if (fa[i]!=fa[y][i])
            x=fa[i],y=fa[y][i];//x,y一起向上跳
    }
    return fa[0];//返回当前节点的父节点，即x,y对应的LCA
}

Tarjan算法求LCA

这是一种离线算法，需要对询问进行处理后再逐步求得所有答案

主要采用并查集的维护方式，自底向上对可以求得的询问进行回答

int n,m,s;
vector<int> e[500010];
vector<pair<int,int>> q[500010];
bool vis[500010];
int fa[500010];
int ans[500010];

int find(int x){
    if (x==fa) return x;
    return fa=find(fa);//路径压缩不影响答案
}

void solve(){
    cin>>n>>m>>s;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if (a==b){
            ans[i]=a;
            continue;
        }
        q[a].push_back({b,i});
        q[b].push_back({a,i});
    }
    for (int i=0;i<=n;i++) fa[i]=i;
    tarjan(s);
    for (int i=1;i<=m;i++) cout<<ans[i]<<endl;
}

递归到底层返回时，查找与这个点有关的询问 [a,b] 如果另外一个节点已经被访问过了，那么就可以计算答案

依靠DFS序得到的公共祖先一定是最近的，因为只有在处理完节点有关的询问后才会回溯到上一层

void tarjan(int x){
    vis=1;//标记访问
    for (auto v:e){
        if (vis[v]) continue;
        tarjan(v);//递归
        fa[v]=x;
    }
    for (auto it:q){
        if (vis[it.first])//如果另外一个节点也被访问过
            ans[it.second]=find(it.first);//计算答案
    }
}

树链剖分求LCA

重儿子：父节点所有儿子中子树节点最多的儿子，轻儿子：父节点除开重儿子之外的儿子

重边：连接父节点与他的重儿子的边，轻边：连接父节点与他轻儿子的边

重链：多条连续重边构成的路径

引理：

  • 一棵树能够被剖分为若干条重链
  • 重链的顶点一定是一个轻儿子
  • 树上任意一条连接 $n$ 个节点路径可以被切分为不超过 $\log n$ 条重链

HLD

图引自OIWIKI

vector<int> e[500010];
int dep[500010],sz[500010];
int fa[500010],son[500010];
int top[500010];

void solve(){
    cin>>n>>m>>s;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(s,0);
    dfs2(s,s);
    for (int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
}

需要两次DFS处理出不同的信息

void dfs1(int x,int p){
    dep=dep[p]+1;
    fa=p;
    sz=1;
    for (auto v:e){
        if (v==p) continue;
        dfs1(v,x);
        sz+=sz[v];
        if (sz[son]<sz[v]) son=v;//v的子树大小如果比之前记录的重儿子更大，那么更新重儿子
    }
}

首先需要通过第一次 DFS 处理出每个节点的深度，父亲以及他形成的子树的大小

son[i] 数组记录 i 节点的重儿子编号，通过每个儿子的子树大小进行更新

void dfs2(int x,int t){
    top=t;
    if (!son) return;//如果没有重儿子，说明x节点为叶子节点，直接返回
    dfs2(son,t);//向下沿着重儿子扩展重链
    for (auto v:e){
        if (v==fa||v==son) continue;
        dfs2(v,v);/沿着轻儿子新开一条重链
    }
}

第二次 DFS 开始树链剖分，top[i] 记录 i 节点所在重链的顶点

枚举 $i$ 节点所有儿子时，如果该儿子是重儿子就继承父节点所在重链的顶点，如果是轻儿子，那么就从这个轻儿子开始重新建立一条重链

int lca(int x,int y){
    while(top!=top[y]){
        if (dep[top]<dep[top[y]]) swap(x,y);//保证x节点深度最大
        x=fa[top];//沿着重链向上跳
    }
    return dep<dep[y]?x:y;//返回LCA
}

计算 LCA 的原理是让询问的两个节点 $x,y$ 沿着重链向上跳，当跳到同一条重链上时深度较小的点为 LCA

与倍增法类似，每次都选择深度较大的节点向上跳