LCA--最近公共祖先

firstlight Lv2
  2023-10-04 11:33 2023-10-04 11:33 创建   2025-01-22 22:41:04 2025-01-22 22:41:04 更新      

最近公共祖先 LCA :

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。

(一) LCA 的倍增算法:

倍增算法：

倍增法求实质上是用二进制拼凑出两个节点的最近公共祖先的深度，进而求出其最近公祖先的方法
倍增法求LCA.png

基本思想:

1.预处理数组和数组：

表示节点的第层的祖先，如

表示节点所在的层数

的作用是实现倍增

的作用是实现两个节点位置的比较

2.跳的方式：

假设要向上跳步，从大到小遍历向上跳的步数的指数(即中的)，如果跳上去后没有超过，则说明可以向上跳，则跳上去，这样跳数次后，一定会跳到的位置上 (二进制表示的必然性)。由于的最大值是提前算好的，所以在跳过去后，剩余的路程一定小于跳上去时的的值，所以不会重复遍历，计算次数一定小于。

3.函数：

首先将要求的两个节点中较低的一个跳到与另一个节点深度相同的位置
然后如果两个节点在同一位置，则说明已经到达最近公共祖先的位置，直接返回即可
否则将两个节点同时向上跳同样的高度，一直到两个节点是同一个节点的子节点为止。

为什么不跳到同一节点上：跳到同一节点上时可能已近跳过最近公共祖先，而是跳到了深度更高的节点上。在代码实现时，用两节点向上跳到的位置不相等表示他们可以向上跳，这样一定会跳到同一节点的下面的位置上 (二进制表示的必然性)
最后返回它们其中一个向上跳步的位置 (即当前节点的父节点) 即可

4.哨兵：

将赋为0
这样可以避免节点跳到根节点以上的情况;

以及在两个节点同时跳，两个节点同时跳过根节点时，使得两个节点的值相等，不保留

Code:

以AcWing.1172为例

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
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 40010;

int n, m;
int h[N], e[N], ne[N], idx;
int root;
int depth[M], fa[M][17];
queue<int> q;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for(int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if(depth[a] < depth[b]) swap(a, b);
    for(int i = 15; i >= 0; i -- )
        if(depth[fa[a][i]] >= depth[b]) // 如果节点a跳到根节点以上,fa[a][i]的值为0(根据上面的计算可知)，所以depth[fa[a][i]]的值为0，一定比任何节点要高
            a = fa[a][i];
    
    if(a == b) return a;
    
    for(int i = 15; i >= 0; i -- )
        if(fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    
    return fa[a][0];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(b == -1) root = a;
        else add(a, b), add(b, a);
    }
    
    bfs();
    
    scanf("%d", &m);
    while(m -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        int p = lca(x, y);
        if(x == p) printf("1\n");
        else if(y == p) printf("2\n");
        else printf("0\n");
    }
    return 0;
}

(二) LCA 的 Tarjan (离线)算法：

TarjanlLCA.png

基本思想：

在深搜时将数中的所有节点分为三类：

  1. 已经搜索过的点 状态为2 绿色
  2. 正在搜索的点 状态为1 红色
  3. 还未搜索的点 状态为0 蓝色

将状态为 2 的点通过并查集索引到其状态为 1 的祖先上(将绿色的节点放在其红色的祖先节点上)
在搜索过程中，将所有的节点的与之在同一查询的另一个节点用并查集查询到它状态为 1 的祖先节点上，则这个点一定是两个点的最近公共祖先

Code:

以AcWing1171.距离为例

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20010, M = N * 2;
typedef pair<int, int> PII;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
int ans[N];
int st[N];
int p[N];
vector<PII> query[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void Tarjan(int u)
{
    st[u] = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            Tarjan(j);
            p[j] = u;
        }
    }
    
    for(auto item : query[u])
    {
        int t = item.first, id = item.second;
        if(st[t] == 2)
        {
            int anc = find(t);
            ans[id] = dist[u] + dist[t] - dist[anc] * 2;
        }
    }
    
    st[u] = 2;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    dfs(1, -1);
    
    for(int i = 1; i <= m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
            
    }
    
    for(int i = 1; i <= n; i ++ ) p[i] = i;
    
    Tarjan(1);
    
    for(int i = 1; i <= m; i ++ ) printf("%d\n", ans[i]);
    return 0;
}
  • 标题: LCA--最近公共祖先
  • 作者: firstlight
  • 创建于 : 2023-10-04 11:33:00
  • 更新于 : 2025-01-22 22:41:04
  • 链接: https://blog.firstlightport.top/posts/LCA/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
LCA--最近公共祖先
  1. 最近公共祖先 LCA :
    1. (一) LCA 的倍增算法:
  2. Code:
    1. (二) LCA 的 Tarjan (离线)算法：
    2. Code: