4 条题解

  • 0
    @ 2026-7-6 20:53:22

    最近公共祖先（LCA）

    发布时间：2024-05-26 16:47:21
    阅读量：2.7k
    字数：1.1k
    阅读时间：约7分钟

    最近公共祖先

    最近公共祖先（LCA）指的是在有根树中，两个节点的公共祖先中深度最大的那个。

    对于 LCA 问题，有多种算法可以求解。

    倍增

    过程

    预处理每个节点 uu，用 fa[u][i]fa[u][i] 表示 uu 的 2i2^i 级祖先。

    对于每个节点 uu 和 ii，有 fa[u][i]=fa[fa[u][i−1]][i−1]fa[u][i] = fa[fa[u][i-1]][i-1]。特别的，fa[u][0]fa[u][0] 是 uu 的父亲节点。

    求 LCA 时，先把两个节点调整到同一深度，然后一起向上跳。

    当两个节点不相同时，若它们的 2i2^i 级祖先不同，则同时向上跳 2i2^i 步。最后它们的父亲节点就是 LCA。

    时间复杂度

    预处理 O(nlog⁡n)O(n \log n)，每次查询 O(log⁡n)O(\log n)。

    代码

    #include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int LOG = 20;

int n, m, s;
int fa[N][LOG], dep[N];
vector<int> G[N];

void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for (int i = 1; i < LOG; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : G[u]) {
        if (v != f) {
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int i = LOG - 1; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = LOG - 1; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs(s, 0);
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    
    return 0;
}

    树链剖分

    过程

    树链剖分可以将树分割成若干条链，使得树上的每条路径都可以被分割成 O(log⁡n)O(\log n) 条链上的区间。

    求 LCA 时，不断将深度较大的节点跳到其所在链的顶端的父亲节点，直到两个节点在同一条链上。

    时间复杂度

    预处理 O(n)O(n)，每次查询 O(log⁡n)O(\log n)。

    代码

    #include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m, s;
vector<int> G[N];
int fa[N], dep[N], sz[N], son[N];
int top[N];

void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    for (int v : G[u]) {
        if (v != f) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) {
                son[u] = v;
            }
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) {
        dfs2(son[u], t);
        for (int v : G[u]) {
            if (v != fa[u] && v != son[u]) {
                dfs2(v, v);
            }
        }
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            swap(u, v);
        }
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs1(s, 0);
    dfs2(s, s);
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    
    return 0;
}

    欧拉序 + ST表

    过程

    欧拉序是指 DFS 过程中，每次进入一个节点和离开一个节点时都记录一次该节点。

    显然，节点数为 nn 的树的欧拉序长度为 2n−12n - 1。

    两个节点的 LCA 就是欧拉序中第一次出现这两个节点的位置之间深度最小的节点。

    这个性质可以用 ST 表来维护。设 pos[u]pos[u] 表示节点 uu 第一次出现的位置，dfndfn 表示欧拉序。那么 LCA 就是 dfn[pos[u],pos[v]]dfn[pos[u], pos[v]] 中深度最小的节点。

    时间复杂度

    预处理 O(nlog⁡n)O(n \log n)，查询 O(1)O(1)。

    代码

    #include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int LOG = 20;

int n, m, s;
vector<int> G[N];
int dfn[N * 2], pos[N], dep[N], st[N * 2][LOG];
int cnt;

void dfs(int u, int f, int d) {
    dfn[++cnt] = u;
    pos[u] = cnt;
    dep[u] = d;
    for (int v : G[u]) {
        if (v != f) {
            dfs(v, u, d + 1);
            dfn[++cnt] = u;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs(s, 0, 1);
    
    for (int i = 1; i <= cnt; i++) {
        st[i][0] = i;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= cnt; i++) {
            int x = st[i][j - 1], y = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = dep[dfn[x]] < dep[dfn[y]] ? x : y;
        }
    }
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        int l = pos[u], r = pos[v];
        if (l > r) {
            swap(l, r);
        }
        int k = log2(r - l + 1);
        int x = st[l][k], y = st[r - (1 << k) + 1][k];
        cout << dfn[dep[dfn[x]] < dep[dfn[y]] ? x : y] << '\n';
    }
    
    return 0;
}

    DFS序 + ST表

    过程

    DFS 序是指 DFS 过程中，每次进入一个节点时记录该节点。

    对于两个节点 u,vu, v，不妨设 dfn[u]<dfn[v]dfn[u] < dfn[v]。u,vu, v 的 LCA 一定在 uu 的子树中（不含 uu 的祖先）或 vv 的祖先上从 uu 出发第一个满足 dfndfn 值在 [dfn[u],dfn[v]][dfn[u], dfn[v]] 范围内的节点。所以 LCA 就是 dfndfn 值在 [dfn[u],dfn[v]][dfn[u], dfn[v]] 范围内深度最小的节点。

    时间复杂度

    预处理 O(nlog⁡n)O(n \log n)，查询 O(1)O(1)。

    代码

    #include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int LOG = 20;

int n, m, s;
vector<int> G[N];
int dfn[N], pos[N], dep[N], st[N][LOG];
int cnt;

void dfs(int u, int f, int d) {
    dfn[++cnt] = u;
    pos[u] = cnt;
    dep[u] = d;
    for (int v : G[u]) {
        if (v != f) {
            dfs(v, u, d + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs(s, 0, 1);
    
    for (int i = 1; i <= n; i++) {
        st[i][0] = i;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int x = st[i][j - 1], y = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = dep[dfn[x]] < dep[dfn[y]] ? x : y;
        }
    }
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        int l = pos[u], r = pos[v];
        if (l > r) {
            swap(l, r);
        }
        int k = log2(r - l + 1);
        int x = st[l][k], y = st[r - (1 << k) + 1][k];
        cout << dfn[dep[dfn[x]] < dep[dfn[y]] ? x : y] << '\n';
    }
    
    return 0;
}

    Tarjan

    过程

    Tarjan 算法是一种离线算法，利用 DFS 和并查集来求解 LCA。

    具体过程如下：

    1. 任选一个节点为根，从根开始 DFS。
    2. 对于每个节点 uu，先递归处理 uu 的所有子节点，然后将 uu 加入并查集。
    3. 对于每个询问 (u,v)(u, v)，若 vv 已经被访问过，则 uu 和 vv 的 LCA 就是 vv 在并查集中的祖先中深度最大的那个。

    这个算法的正确性在于，我们处理完 uu 后，会回溯到它的 LCA 再往下走，所以此时 uu 在并查集中的祖先就是它们的 LCA。

    时间复杂度

    时间复杂度 O(n+m)O(n + m)，其中 nn 为节点数，mm 为询问数。

    代码

    #include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, m, s;
vector<int> G[N];
vector<pair<int, int>> Q[N];
int fa[N], dep[N], ans[N];
bool vis[N];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void dfs(int u, int f) {
    fa[u] = u;
    vis[u] = true;
    for (int v : G[u]) {
        if (v != f) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
            fa[v] = u;
        }
    }
    for (auto [v, id] : Q[u]) {
        if (vis[v]) {
            ans[id] = find(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        Q[u].push_back({v, i});
        Q[v].push_back({u, i});
    }
    
    dfs(s, 0);
    
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}

    总结

    算法 预处理时间复杂度 查询时间复杂度 空间复杂度 优点 缺点
    倍增 O(nlog⁡n)O(n \log n) O(log⁡n)O(\log n) O(nlog⁡n)O(n \log n) 实现简单 查询较慢
    树链剖分 O(n)O(n) O(n)O(n) 实现简单，可以处理路径问题
    欧拉序 + ST表 O(nlog⁡n)O(n \log n) O(1)O(1) O(nlog⁡n)O(n \log n) 查询快 空间较大
    DFS序 + ST表
    Tarjan O(n+m)O(n + m) O(1)O(1) (离线) O(n+m)O(n + m) 时间复杂度最优 离线算法

    文章作者：imnks
    文章链接：https://www.imnks.com/5847.html
    版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

    • 0
      @ 2026-6-20 16:08:55 

      // 树链剖分 O(mlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=500010;
int n,m,s;
vector<int> e[N];

// 树剖求LCA
int fa[N],dep[N],siz[N],son[N],top[N];

void dfs1(int x,int f){ //搞fa,dep,siz,son
  fa[x]=f; dep[x]=dep[f]+1; siz[x]=1;
  for(int y:e[x])if(y!=f){
    dfs1(y,x);
    siz[x]+=siz[y];
    if(siz[son[x]]<siz[y]) son[x]=y;
  }
}
void dfs2(int x,int t){ //搞top
  top[x]=t;             //记录链顶
  if(son[x]) dfs2(son[x],t); //搜重儿子
  for(int y:e[x])if(y!=fa[x]&&y!=son[x]) dfs2(y,y); //搜轻儿子
}
int lca(int x,int y){
  while(top[x]!=top[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
  return dep[x]<dep[y]?x:y; //x,y跳到同条重链，浅的为LCA
}

int main(){
  scanf("%d%d%d",&n,&m,&s);
  for(int i=1,x,y; i<n; i++){
    scanf("%d%d",&x,&y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs1(s,0);
  dfs2(s,s);
  for(int x,y;m--;){
    scanf("%d%d",&x,&y);
    printf("%d\n",lca(x,y));
  }
}
      • 0
        @ 2026-6-20 16:06:32 

        // Tarjan算法 O(n+m)
#include<bits/stdc++.h>
using namespace std;

const int N=500005,M=2*N;
int n,m,s,a,b;
vector<int> e[N];
vector<pair<int,int>> query[N];
int fa[N],vis[N],ans[M]; 

int find(int x){
  if(x==fa[x]) return x;
  return fa[x]=find(fa[x]);
}
void tarjan(int x){
  vis[x]=true; //标记x已访问
  for(auto y:e[x]){
    if(!vis[y]){
      tarjan(y);
      fa[y]=x; //回到x时指向x
    }        
  }
  for(auto q : query[x]){ //离开x时找LCA
    int y=q.first,i=q.second;
    if(vis[y])ans[i]=find(y);
  }
}
int main(){
  scanf("%d%d%d",&n,&m,&s);
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  for(int i=1;i<=m;i++){
    scanf("%d%d",&a,&b);
    query[a].push_back({b,i});
    query[b].push_back({a,i});
  }
  for(int i=1;i<=N;i++)fa[i]=i;
  tarjan(s);
  for(int i=1; i<=m; i++)
    printf("%d\n",ans[i]);
}
        • 0
          @ 2025-10-8 16:50:31

          D09 倍增算法 P3379【模板】最近公共祖先（LCA）——信息学奥赛算法
          st表求LCA：

          #include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N]; 
int D,dep[N],st[N][21];
void dfs(int x,int xfa)
{
    dep[x]=dep[xfa]+1;
    st[x][0]=xfa;for(int i=1;i<=D;i++)st[x][i]=st[ st[x][i-1] ][i-1];
    for(int y:G[x])if(y!=xfa)
        dfs(y,x);
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y); 
    for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y] )x=st[x][i];
    if(x==y) return x;
	for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
    return st[x][0];
}
int main()
{
    //freopen("b9.in","r",stdin);
    int n,m,rt;scanf("%d%d%d",&n,&m,&rt);
    for(int i=1,x,y;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    D=log2(n);memset(dep,0,sizeof(dep));memset(st,0,sizeof(st));
    dfs(rt,0);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}
          • 1

          D09D10D11【模板】最近公共祖先（LCA）

          信息

          ID
          461
          时间
          2000ms
          内存
          512MiB
          难度
          8
          标签
          递交数
          499
          已通过
          89
          上传者
          1. Language
          2. 兼容模式
          3. 主题
          3. Worker 0, 9ms
          4. Powered by Hydro v5.0.1 Community