LCA 最近公共祖先

LCA 树上倍增法#

实质是把节点每次向上暴力移动一步变成更加高明的按 ${2^k}$ 步向上移动，借用的是每个数都可进行二进制分解的定理。期间维护一个父节点数组 fa，fa[i][k] 代表 $i$ 向上移动 ${2^k}$ 步的父节点。那我们该如何更新这个父节点呢？显然有 ${2^k=2^{k-1}+2^{k-1}}$ ，就是两次向上移动 ${2^{k-1}}$ 步，因此可以用 fa[fa[i][k - 1]][k - 1] 来递归更新。

初始化时使用宽搜，把所有点的深度更新一遍。注意要设置一个类似于 $\texttt{Splay}$ 中的边界节点，深度设为 ${0}$ （根节点深度为 ${1}$ ），以防倍增移动时发生超出根节点的情况。

对于 $\texttt{LCA}$ 的求解，基本思路是把待求的两个节点先挪到同一位置上，然后共同向上移动，当二者根节点已经相同时就可以返回这个根节点了。特殊地，如果上移到同一深度时两点已经重合，则直接返回两点中的其中一个。

模板：

1
#include <bits/stdc++.h>
2
#define N 500010
3
using namespace std;
4

5
struct Edge {
6
    int to, ne;
7
} edges[N << 1];
8
int h[N], idx = 0;
9

10
int fa[N][22];
11
int dep[N];
12

13
int root = 0;
14

15
void add(int a, int b) {
16
    idx++;
17
    edges[idx].to = b;
18
    edges[idx].ne = h[a];
19
    h[a] = idx;
20
}
21

22
void init() {
23
    memset(dep, 0x3f, sizeof dep);
24
    queue<int> q;
25
    dep[0] = 0;
26
    dep[root] = 1;
27
    q.push(root);
28
    while (!q.empty()) {
29
        int t = q.front();
30
        q.pop();
31
        for (int i = h[t]; ~i; i = edges[i].ne) {
32
            int j = edges[i].to;
33
            if (dep[j] > dep[t] + 1) {
34
                dep[j] = dep[t] + 1;
35
                fa[j][0] = t;
36
                q.push(j);
37
                for (int k = 1; k <= 21; k++) {
38
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
39
                }
40
            }
41
        }
42
    }
43
}
44

45
int LCA(int a, int b) {
46
    if (dep[a] < dep[b]) swap(a, b);
47
    for (int k = 21; k >= 0; k--) {
48
        if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
49
    }
50
    if (a == b) return a;
51
    for (int k = 21; k >= 0; k--) {
52
        if (fa[a][k] != fa[b][k]) {
53
            a = fa[a][k];
54
            b = fa[b][k];
55
        }
56
    }
57
    return fa[a][0];
58
}
59

60
int main() {
61
    ios::sync_with_stdio(false);
62
    cin.tie(nullptr);
63
    cout.tie(nullptr);
64

65
    memset(h, -1, sizeof h);
66
    int n, m;
67
    cin >> n >> m >> root;
68
    for (int i = 1; i < n; i++) {
69
        int x, y;
70
        cin >> x >> y;
71
        add(x, y);
72
        add(y, x);
73
    }
74
    init();
75
    while (m--) {
76
        int a, b;
77
        cin >> a >> b;
78
        cout << LCA(a, b) << endl;
79
    }
80
    return 0;
81
}

再探次小生成树#

一个半月前，我写了次小生成树的求解方法，当时是将非树边挨个加入进树中，形成一个环，并剔除这个环中最大的树内边，比较这些操作对最小生成树总边权的贡献从而得到原树的非严格次小生成树（若需要严格次小生成树则需要维护环上次大边）。其中为了找到环内最/次大边，我们使用了指数级别的 $\texttt{DFS}$ ，今天学习了倍增 $\texttt{LCA}$ ，可以用来优化这一方案。

洛谷 P4180 [BJWC2010] 严格次小生成树#

题目地址：P4180

题目难度：提高+/省选-

题目来源：北京 2010 各省省选

依然是先求出最小生成树以及它的总边权，但是对于最大/次大边权的查询，考虑使用倍增 $\texttt{LCA}$ 做法。

联系到递归求解 ${2^k}$ 步父节点时的操作，其实维护树上最/次大边权也可如此。同样是把 ${2^k}$ 拆解成两个 ${2^{k-1}}$ 步，然后对于第一次移动，可以继续向下递归找到最/次大边权；第二次移动同理。最/次大值通过遍历就很容易找出来了，具体方法如下：

如果当前值严格大于维护的最大值，更新最大值为当前值，把次大值赋为原先的最大值。
如果当前值严格小于最大值且严格大于次大值，那么更新次大值为当前值。

对走两步分别得到的四个最/次大值执行遍历，就可以得到全局最/次大值了。在倍增 $\texttt{LCA}$ 过程中，我们把（最小生成树中）节点移动过程中经历的所有树内边的最大值和次大值保存起来，解出全局最/次大值，并与当前升序遍历到的非树边权作比较，得出新边的贡献，即可解得次小生成树的权值。注意去除自环。

其中 d1[a][k] 代表节点 $a$ 向上移动 ${2^k}$ 步经过的边的最大权值，d2[a][k] 则是相应的次大权值。

代码过长（177行）

维护树上差分#

AcWing 352. 闇くらの連ねん鎖さ#

题目地址：AcWing 352

题目难度：困难

传说中的暗之连锁被人们称为 Dark。
Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。
经过研究，你发现 Dark 呈现无向图的结构，图中有 $N$ 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。
Dark 有 $N-1$ 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。
另外，Dark 还有 $M$ 条附加边。
你的任务是把 Dark 斩为不连通的两部分。
一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。
一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。
但是你的能力只能再切断 Dark 的一条附加边。
现在你想要知道，一共有多少种方案可以击败 Dark。
注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。
输入格式：
第一行包含两个整数 $N$ 和 $M$ 。
之后 $N-1$ 行，每行包括两个整数 $A$ 和 $B$ ，表示 $A$ 和 $B$ 之间有一条主要边。
之后 $M$ 行以同样的格式给出附加边。
输出格式：
输出一个整数表示答案。
数据范围：
$N\leq10^5$ ， $M\leq2\times10^5$ ，数据保证答案不超过 ${2^{31}-1}$ 。

假如树内边（主要边）用黑色表示，非树边（附加边）用红色表示。边上的数字代表：在砍断当前边的情况下还需要砍断多少附加边才能将图分成两部分（默认 ${0}$ ）。事实上，当图中添加了一组附加边，它所连接的两个树内点会和树内若干点组成一个环，并且这个环一定会过两点的最近公共祖先。我们这时从下往上，把环内边上的计数增加 ${1}$ ，就可得到如上的图。根据题意，显然有：

当该边计数为 ${0}$ 时，砍断当前边后，任意砍断一条附加边即可，答案累加 $M$
当该边计数为 ${1}$ 时，砍断当前边后，只能砍断特定的一条附加边，答案累加 ${1}$
当该边计数大于 ${1}$ 时，因为最多只能砍两刀，因此不能通过砍当前主要边击败 Dark，答案不变

如何更新边上的计数呢？运用树上差分的思想——把权值的差分存储在图上，和序列差分一样，如果想要给某个区间内所有的数加减某个数，则只需在左端点和右端点加/减这个数，然后右端点的右边再减/加这个数，最后求前缀和即可得到原数；树上差分也很类似，我们在附加边连接的两个点上更改数值，然后找到它们的最近公共祖先，减去两倍的值即可。

1
#include <bits/stdc++.h>
2
#define N 100010
3
using namespace std;
4

5
struct Edge {
6
    int to, ne;
7
} edges[N << 1];
8
int h[N], idx = 0;
9
int fa[N][20], depth[N];
10
int dist[N];
11
int m, ans = 0;
12

13
void add(int a, int b) {
14
    idx++;
15
    edges[idx].to = b;
16
    edges[idx].ne = h[a];
17
    h[a] = idx;
18
}
19

20
void init(int root) {
21
    memset(depth, 0x3f, sizeof depth);
22

23
    queue<int> q;
24
    depth[0] = 0;
25
    depth[root] = 1;
26
    q.push(1);
27
    while (!q.empty()) {
28
        int t = q.front();
29
        q.pop();
30
        for (int i = h[t]; ~i; i = edges[i].ne) {
31
            int j = edges[i].to;
32
            if (depth[j] > depth[t] + 1) {
33
                depth[j] = depth[t] + 1;
34
                fa[j][0] = t;
35
                q.push(j);
36
                for (int k = 1; k <= 19; k++) {
37
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
38
                }
39
            }
40
        }
41
    }
42
}
43

44
int LCA(int a, int b) {
45
    if (depth[a] < depth[b]) swap(a, b);
46
    for (int k = 19; k >= 0; k--) {
47
        if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
48
    }
49
    if (a == b) return a;
50
    for (int k = 19; k >= 0; k--) {
51
        if (fa[a][k] != fa[b][k]) {
52
            a = fa[a][k];
53
            b = fa[b][k];
54
        }
55
    }
56
    return fa[a][0];
57
}
58

59
int dfs(int u, int f) {
60
    int res = dist[u]; // 当前记录的差分权
61
    for (int i = h[u]; ~i; i = edges[i].ne) {
62
        int j = edges[i].to;
63
        if (j == f) continue;
64
        int t = dfs(j, u); // 获得子树的差分权值
65
        if (t == 0) ans += m;
66
        else if (t == 1) ans++;
67
        res += t; // 向上更新，累加子树差分权
68
    }
69
    return res;
70
}
71

72
int main() {
73
    ios::sync_with_stdio(false);
74
    cin.tie(nullptr);
75
    cout.tie(nullptr);
76

77
    memset(h, -1, sizeof h);
78

79
    int n;
80
    cin >> n >> m;
81
    for (int i = 1; i < n; i++) {
82
        int a, b;
83
        cin >> a >> b;
84
        add(a, b);
85
        add(b, a);
86
    }
87
    init(1);
88
    for (int i = 1; i <= m; i++) {
89
        int a, b;
90
        cin >> a >> b;
91
        int p = LCA(a, b);
92
        dist[a]++, dist[b]++, dist[p] -= 2; // 维护树上差分
93
    }
94
    dfs(1, -1);
95
    cout << ans << endl;
96
    return 0;
97
}

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

LCA 树上倍增法#

再探次小生成树#

洛谷 P4180 [BJWC2010] 严格次小生成树#

维护树上差分#

AcWing 352. 闇くらの連ねん鎖さ#

支持与分享

评论区

音乐

目录