Sakana~
0%

【算法学习笔记】04 最近公共祖先LCA

发表于 更新于 分类于

LCA基础知识

【算法学习笔记】04 最近公共祖先LCA

原理

顾名思义，就是求两点的最近公共祖先（自己也是自己的祖先）。
也就是两点在走到根节点的路径上最先遇到的共同的点。

向上标记法

比较贴定义的原始方法。
一点先向 root 走，走过的点标记一下；然后另一点也往 root 走，走到的第一个被标记的点为二者的 LCA。时间复杂度为 O(n)

倍增法

1. 首先需要记录两个变量

2. 将两点跳到同一层

3. 让两个点一直往上跳，直到跳到 $LCA$ 的下一层（儿子那层）

Tarjan —— 离线求 LCA

优化向上标记法

dfs 时，把点分为三大类：

1
2
3
0. 还没搜索的
1. 正在搜索的
2. 已经完全搜完的(子树也搜完了)

基于 RMQ

板子

倍增法

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
void bfs (int root) {
    memset (depth, 0x3f, sizeof depth); //记得
    queue <int> q;
    q.push (root);
    depth[root] = 1, depth[0] = 0;

    while (!q.empty()) {
        int t = q.front();
        q.pop ();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push (j);
                f[j][0] = t;
                for  (int k = 1; k <= 15; k++) {
                    f[j][k] = f[f[j][k-1]][k-1];
                }
            }
        }
    }
}

int lca (int a, int b) {
    if (depth[a] < depth[b])    swap (a, b); //确保a往上跳
    for (int k = 15; k >= 0; k--) {
        if (depth[f[a][k]] >= depth[b]) { //注意是>=
            a = f[a][k];
        }
    }
    if (a == b)     return a;
    for (int k = 15; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            a = f[a][k], b = f[b][k];
        }
    }
    return f[a][0];
}

Tarjan 离线做法

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
void dfs (int v, int u) {  //1, -1
    for (int i = h[v]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == u) continue;
        d[j] = d[v] + w[i];
        dfs (j, v);
    }
}

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

void tarjan (int u) {  //1
    vis[u] = 1; //正在搜
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (vis[j]) continue;
        tarjan(j);
        fa[j] = u; //合并
    }

    for (auto i : q[u]) {
        int v = i.first, id = i.second;
        if (vis[v] == 2) {
            int p = find(v);
            ans[id] = d[u] + d[v] - 2*d[p];
        }
    }

    vis[u] = 2; //搜过了
}

例题

前面两个给过板子的题就不放了

严格次小生成树

https://www.luogu.com.cn/problem/P4180
好耶，是紫题

定理

对于一个无向图，如果存在最小生成树和（严格）次小生成树，那么对于任何一颗最小生成树，都存在一颗（严格）次小生成树，使得这两棵树只有一条边不同

原理

即替换后增量最小的边为答案

就相当于是在最小生成树上面加一个多余的边，然后把这条边和原 MST 中的最大边与次大边作比较（两种替换的可能性），则次小生成树权值之和可能为：

  1. MST+ 多余边 - 最大权值边
  2. MST + 多余边 - 次大权值边

如何快速计算路径上的最大边和次大边

Code

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
#define int long long 

using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5, inf = 0x3f3f3f3f;
int fa[N], dist[N*2], n, m;
int h[N], e[M], ne[M], w[M], idx;
int depth[N], f[N][17], d1[N][17], d2[N][17]; //最大，次大

struct Node {
    int a, b, w;
    bool used;
    bool operator<(const Node &t) const {
        return w < t.w;
    }
}E[M];

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

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

int kruscal () {
    for (int i = 1; i <= n; i++)    fa[i] = i;
    sort (E, E + m);
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int a = E[i].a, b = E[i].b, w = E[i].w;
        int pa = find (a), pb = find (b);
        if (pa != pb) {
            fa[pa] = pb;
            ans += w;
            E[i].used = true; //标记为树边
        }
    }
    return ans;
}

void build () {
    memset (h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        if (!E[i].used) continue;
        int a = E[i].a, b = E[i].b, w = E[i].w;
        add (a, b, w), add (b, a, w);
    }
    //build MST
}

void bfs () {
    memset (depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    queue <int> q;
    q.push (1);

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j]  =depth[t] + 1;
                q.push (j);
                f[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -inf;
                for (int k = 1; k <= 16; k++) {
                    int anc = f[j][k-1];
                    f[j][k] = f[anc][k-1];
                    //j跳到anc,anc接着跳
                    int dis[] = {d1[j][k-1], d2[j][k-1], d1[anc][k-1], d2[anc][k-1]};
                    d1[j][k] = d2[j][k] = -inf;
                    for (int u = 0; u < 4; u++) {
                        int d = dis[u];
                        if (d > d1[j][k])   d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if (d != d1[j][k] && d > d2[j][k])     d2[j][k] = d; //严格次大值
                    }
                }
            }
        }
    }
    //LCA预处理
}

int lca (int a, int b, int w) {
    int cnt = 0;
    if (depth[a] < depth[b])    swap (a, b);
    for (int k = 16; k >= 0; k--) {
        if (depth[f[a][k]] >= depth[b]) {
            dist[cnt++] = d1[a][k];
            dist[cnt++] = d2[a][k];
            a = f[a][k]; //jmp
        }
    }

    if (a != b) {
        for (int k = 16; k >= 0; k--) {
            if (f[a][k] == f[b][k])     continue;
            dist[cnt++] = d1[a][k];
            dist[cnt++] = d2[a][k];
            dist[cnt++] = d1[b][k];
            dist[cnt++] = d2[b][k];
            a = f[a][k], b = f[b][k];
        }
        dist[cnt++] = d1[a][0];
        dist[cnt++] = d1[b][0];
    }

    int dist1 = -inf, dist2 = -inf;
    for (int i = 0; i < cnt; i++) {
        int d = dist[i];
        if (d > dist1)  dist2 = dist1, dist1 = d;
        else if (d != dist1 && d > dist2)   dist2 = d;
    }

    if (w > dist1)  return w - dist1;
    if (w > dist2)  return w - dist2;
    return inf;
}

signed main () {
    ios::sync_with_stdio (0);cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        E[i] = {a, b, c};
    }

    int sum = kruscal();
    build(), bfs();

    int ans = 1e18;
    for (int i = 0; i < m; i++) {
        if (E[i].used)  continue;
        int a = E[i].a, b = E[i].b, w = E[i].w;
        ans = min (ans, sum + lca (a, b, w));
    }

    cout << ans;
}

彩蛋：

对于我这种菜鸟来说，这码量还是蛮大的

闇の連鎖

https://www.acwing.com/problem/content/description/354/

题意：砍两刀，第一次斩树边，第二次斩非树边。砍成两半

如图，对于环上的每一条树边来说，如果想要使得它砍完之后，图不连通，那么还要砍掉这个环上的非树边

枚举所有非树边，然后把环上经过的树边+1。树边上的权值就表示砍完这个树边后还需要看多少条非树边

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
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;
const int N = 100000 + 5, M = N*2;
int h[N], e[M], ne[M], idx;
int depth[N], f[N][17];
int n, m;
int d[N], ans;

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

void bfs (int root) {
    memset (depth, 0x3f, sizeof depth);
    queue <int> q;
    q.push (root);
    depth[root] = 1, depth[0] = 0;

    while (!q.empty()) {
        int t = q.front();
        q.pop ();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q.push (j);
                f[j][0] = t;
                for  (int k = 1; k <= 16; k++) {
                    f[j][k] = f[f[j][k-1]][k-1];
                }
            }
        }
    }
}

int lca (int a, int b) {
    if (depth[a] < depth[b])    swap (a, b); //确保a往上跳
    for (int k = 16; k >= 0; k--) {
        if (depth[f[a][k]] >= depth[b]) { //注意是>=
            a = f[a][k];
        }
    }
    if (a == b)     return a;
    for (int k = 16; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            a = f[a][k], b = f[b][k];
        }
    }
    return f[a][0];
}

int dfs (int u, int fa) {
    int res = d[u];
    for  (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) {
            int s = dfs (j, u);
            if (!s) ans += m;
            else if (s == 1)    ans ++;
            res += s;

        }
    }
    return res;
}

int main () {
    ios::sync_with_stdio (0);cin.tie(0);cout.tie(0);
    memset (h, -1, sizeof h);
    cin >> n >> m;
    int root;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        add (a, b), add (b, a);  
    }

    bfs (1); //预处理两个数组

     for (int i = 0; i < m; i ++ ) {
        int a, b;
        cin >> a >> b;
        int p = lca (a, b);
        d[a] ++, d[b] ++, d[p] -= 2;
    }

    dfs (1, -1);
    cout << ans;
}