answerend42的Blog 主页归档标签分类关于
P3379 【模板】最近公共祖先（LCA）
|题解
字数总计: 2.3k|阅读时长: 10 分钟

update on 2020.4.5 新增 tarjan 算法。

前言

​ LCA（Lowest Common Ancestor），即最近公共祖先。在一张图中，要找到两个节点的最近公共祖先，最朴素的算法就是分别从两个节点一层一层向上寻找，直到跳到一个相同的点，这个点就是两者的最近公共祖先。这样查找花费的时间代价太大，我们难以承受，于是就有了几种求LCA的算法。

倍增

​ 关于倍增入门

​ 倍增刚开始学习真的是个很令人讨厌的东西，当我第一次看倍增相关的知识时，我很难理解，但是仔细一想其实不难。我们想象自己就是那只小白兔，尝试跳 1,2,4,8,……($2^0,2^1,2^2,2^3,……,2^n$)步,如果这一步跳跃比目标大，就换用更小的一步，如果换了之后小于目标，就跳这么一步，从新位置开始重复上述过程直至到达目标。

LCA（倍增）

​ 我们注意到，倍增可以看作是“跳步”，而我们之前所采用的朴素算法也类似于跳步（只不过每次只跳一位），我们能不能将倍增的思想用于寻找最近公共祖先呢？

​ 答案显然是可以的。

预处理

​ 我们既然采用倍增，就需要知道对于每一个点跳 $2^k$ 步会到达何方，这里我们不妨用 f[i][j]来表示从 $i$ 号点出发，跳跃 $2^j$ 步将会到达的点。

​ 同时我们有 $2^2=2^1 \times2^1$ ，以此类推又有 $2^k=2^{k-1}\times2^{k-1}$ ，那么跨越 $2^j$ 个格子也就是先跨越 $2^{j-1}$ 个格子 (f[i][j-1]) 再跨越 $2^{j-1}$ 个格子 (f[f[i][j-1]][j-1]) 。于是有了如下公式

​ 于是，我们预处理 f 数组，并按照上述朴素算法执行向上跳的操作。

​ 可是，这样的算法我们很快能举出反例

​

​ 我们选择16,17两个节点，在尝试跳 $2^2$ 步时共同跳到了1号点，然而1号点并不是最近公共祖先。

​ 看来步子确实不能迈得太大。

​ 我们这里采取的方法是实现判断要跳的点是否为同一个点，如果是，则不跳，那么最终会发现，两个点一直没有跳，那么16,17的父亲也就是自己的最近公共祖先。

代码实现

​ 我们可以通过一个dfs来实现每一个节点的深度表示，儿子节点深度为父亲节点深度+1。同时我们还能够完成对于 f 数组的初始化，不过这里并不是向后跳，而是向着根节点跳（也可以认为是在向上跳）。

​ 给出代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int u,int father)
{
    dep[u]=dep[father]+1;//dep表示深度，通常都是深度深的先跳
    for(int i=1;(1<<i)<=dep[u];i++)//(1<<i) 就是 2^i
    {
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=first[u];i;i=nxt[i])
    {
        int p=v[i];
        if(p==father) continue;//这个判定是为了防止回到父亲节点，因为用了无向边
        f[p][0]=u;
        dfs(p,u);
    }
}

​ 有了这一步，lca 的思维难度便一点都不大了

​ 给出代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lca(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    //保证x的深度>y的深度
    for(int i=20;i>=0;i--)//从2^20到2^0
    {
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
        if(x==y) return x;//重合就不能跳了
    }
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])//跳跃！
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];//最后找到的两点的唯一父亲就是最近公共祖先
}

​ 使用方法

1
2
dfs(root,0);
lca(a,b);

​ 本题就被我们顺利地解决了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int N = 500005,M = 500005 * 2;
int n,m,s;
int v[M],first[N],nxt[M],dep[N],idx,f[N][25];
void add(int x,int y)
{
    idx++;
    v[idx]=y;
    nxt[idx]=first[x];
    first[x]=idx;
}
void dfs(int u,int father)
{
    dep[u]=dep[father]+1;
    for(int i=1;(1<<i)<=dep[u];i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=first[u];i;i=nxt[i])
    {
        int p=v[i];
        if(p==father) continue;
        f[p][0]=u;
        dfs(p,u);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    //保证x的深度>y的深度
    for(int i=20;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
        if(x==y) return x;
    }
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
/*
dfs(root,0);
lca(a,b);
*/
int main()
{
    /*
    LCA 倍增求法 每次选取我们能够跳的最大高度
    如果跳到了同一层级，继续，直到最终不能再使深度变小
    前提 不能相遇
    */
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    dfs(s,0);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}

LCA（tarjan）

Tarjan 这个大神犇又来造福大家了，全新的炫酷 dfs 神奇应用 LCA。

这是一个离线算法，即最终一次性跑完所有查询，原理是通过一次 dfs 实现。

tarjan 算法基本思路：

  1. 任选一个点为根节点，从根节点开始进行DFS。

  2. 标记当前访问到的点 u 已经被访问过。

  3. 寻找与当前点 u 有询问关系的点 v。

  4. 若是 v 已经被访问过了，则可以确认 u 和 v 的最近公共祖先为 v 被合并到的父亲节点 a。

  5. 遍历点 u 的所有子节点 v。

  6. 若 v 还有子节点，返回2，否则下一步。

  7. 合并 v 到 u 上。

具体思路先 gugugu。

给出代码如下

基于 vector 实现（速度较慢，明明是线性算法愣是比倍增慢还 T 了3个点，只能O2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define pb push_back
#define VI vector<int>
struct edge {
    int u,v,lca;
} qe[N];
int n,m,f[N],book[N],a,s;
VI e[N],q[N];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
void tarjan(int x) {
    book[x]=1;
    for(int i=0;i<q[x].size();i++) {
        int idx=q[x][i];
        if(qe[idx].u!=x) a=qe[idx].u;
        else a=qe[idx].v;
        if(book[a]) qe[idx].lca=getf(a);
    }
    for(int i=0;i<e[x].size();i++) {
        int y=e[x][i];
        if(!book[y]) {
            tarjan(y);
            f[y]=x;
        }
    }
}
inline char getcha() {
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    char ch=getcha();int ret=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getcha();}
    while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getcha();}
    return ret*f;
}
int main() {
    n=read(),m=read(),s=read();
    for(int i=1;i<=n-1;i++) {
        int x=read(),y=read();
        e[x].pb(y);e[y].pb(x);
    }
    for(int i=1;i<=m;i++) {
        qe[i].u=read(),qe[i].v=read();
        q[qe[i].u].pb(i);q[qe[i].v].pb(i);
    }
    for(int i=1;i<=n;i++) f[i]=i;
    tarjan(s);
    for(int i=1;i<=m;i++) {
        printf("%d\n",qe[i].lca);
    }
    return 0;
}

基于链式前向星实现（常数小，但是实现比较复杂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7,M= 2 * N;
int idx,first[N],nxt[M],v[M],book[N],f[N],a,n,m,s;
int idx1,q_first[N],q_nxt[M],q_v[M];
struct edge {
    int u,v,lca;
} qe[N];
void add(int x,int y) {
    idx++;
    v[idx]=y;
    nxt[idx]=first[x];
    first[x]=idx;
}
void add_q(int x,int y) {
    idx1++;
    q_v[idx1]=y;
    q_nxt[idx1]=q_first[x];
    q_first[x]=idx1;
}
int getf(int x) {return x==f[x]?x:f[x]=getf(f[x]);}
void tarjan(int x) {
    book[x]=1;
    for(int i=q_first[x];i;i=q_nxt[i]) {
        int qv=q_v[i];
        if(book[qv]) {
            qe[i].lca=getf(qv);
            if(i%2) qe[i+1].lca=qe[i].lca;
            else qe[i-1].lca=qe[i].lca;
        }
    }
    for(int i=first[x];i;i=nxt[i]) {
        int y=v[i];
        if(!book[y]) {
            tarjan(y);
            f[y]=x;
        }
    }
}
inline char getcha() {
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    char ch=getcha();int ret=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getcha();}
    while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getcha();}
    return ret*f;
}
int main() {
    n=read(),m=read(),s=read();
    for(int i=1;i<=n-1;i++) {
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(int i=1;i<=m;i++) {
        qe[i].u=read(),qe[i].v=read();
        add_q(qe[i].u,qe[i].v);add_q(qe[i].v,qe[i].u);
    }
    for(int i=1;i<=n;i++) f[i]=i;
    tarjan(s);
    for(int i=1;i<=m;i++) {
        printf("%d\n",qe[i*2].lca);
    }
    return 0;
}

后记

​ 作者很久之前就想学习 LCA ，并多次查阅 OI Wiki 但实属能力不足，一直没有看懂，非常感谢

这个 教学视频 。可以说是非常直观了。

参考

最近公共祖先 OI Wiki

【manim | 算法】7分钟学会倍增法求解LCA

【白话系列】倍增算法

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/03/01/lg3379/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog！
模板最近公共祖先