LCA DS MST

LCA ———— Least Common Ancestors

如何计算？

  • 深度相同一起跳
  • 深度不同，深度大的跳

显然，一层一层跳复杂度将会来到O(N)

空间换时间 一次多跨几步

联系：ST表
考虑保存2 的幂次级 祖先

于是我们有了一种很棒的倍增做法：

  1. 假设 y 比 x 深，则 y 需要向上跳 a = h(y) - h(x)
  2. 对 a 进行二进制拆分
  3. 令 f[x][i]为结点 x 的 2^i级祖先，则状态转移方程为：f[x][i] = f[f[x][i-1]][i-1]

也就是说，我们可以进行一个ST表的预处理：

1
2
3
4
5
for(int j = 1;j <= 20;j ++){
    for(int i = 1;i <= n;i ++){
        f[i][j] = f[f[i][j-1]][j-1];
    }
}

复杂度是O(NlogN)的

深度相同一起跳

问题在于：深度差未知
不能跳过头，但也不想太保守（一点一点往上挪），争取跳出能跳的 最大的步子

So:以 2 的幂次从大往小尝试

  • 每次跳都确保跳到的点不相同
  • 步长递减到2^0 为止，返回最后点的父亲节点

LCA 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int lca(int x,int y){
    if(dp[x] < dp[y]){
        swap(x,y);
    }
    for(int j = 19;j >= 0;j --){
        if(dp[f[x][i]] >= dp[y]){
            x = f[x][i];
        }
    }
    if(x == y){
        return x;
    }
    for(int j = 19;j >= 0;j --){
        if(dp[f[x][j]] != dp[f[y][j]]){
            x = f[x][j];
            y = f[y][j];
        }
    }
    return f[x][0];
}

应用：树上差分

给定一棵树 n 个节点，有 m 次操作，每次操作给出 u，v 两个节点，将 u-v 路径上的所有点权值 +1。之后查询每个点的点权。

想法：联系树状数组区间修改

差分树上节点加 1 ，代表从根节点到该节点的路径上的节点都加 1

经典例子：清理蜘蛛网

放个题：清理蜘蛛网 ACMOJ
想法一个是图的存储，我一开始试图用树存储，发现整个存储结构一片混乱。无奈最后投向邻接表（注意必须是邻接表而不是邻接矩阵，不然你将无法过编）
还有树上差分（边的差分），更新起点终点（++）和lca点（-= 2）
以及前缀和的计算，result[u] = diff[u] + sum(children diff[sn])
还有体现附加边的作用，骨架边断开的机会分类讨论。
总结：一道很难想也不太好写的题，主播写了至少1个多小时（还是在有思路的情况下）

贴个AC代码

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
#include <iostream>
#include <cmath>
using namespace std;
int n,m;
struct edge {
    edge *next;
    int end;
};
struct ver {
    int value;
    edge *head;
};
ver g[100005];
int fa[100005][21];
int diff[100005];
int dp[100005];
void addEdge(int u,int v) {
    edge *current = new edge;
    current->end = v;
    current->next = g[u].head;
    g[u].head = current;
}
void dfs(int sn,int f,int h) {
    fa[sn][0] = f;
    dp[sn] = h;
    edge *e = g[sn].head;
    while(e != nullptr) {
        if(e->end != f) {
            dfs(e->end,sn,h + 1);
        }
        e = e->next;
    }
}
int lca(int x,int y) {
    if(dp[x] < dp[y]) {
        swap(x,y);
    }
    for(int j = 19;j >= 0;j --) {
        if(dp[fa[x][j]] >= dp[y]) {
            x = fa[x][j];
        }
    }
    if(x == y) {
        return x;
    }
    for(int j = 19;j >= 0;j --) {
        if(fa[x][j] != fa[y][j]) {
            x = fa[x][j];
            y = fa[y][j];
        }
    }
    return fa[x][0];
}
void calculate(int sn,int fa) {
    edge *e = g[sn].head;
    while(e != nullptr) {
        if(e->end != fa) {
            calculate(e->end,sn);
            diff[sn] += diff[e->end];
        }
        e = e->next;
    }
}
int main() {
    cin >> n >> m;
    int u,v;
    for(int i = 1;i <= n;i ++) {
        g[i].head = nullptr;
    }
    for(int i = 1;i < n;i ++) {
        cin >> u >> v;
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,0,0);
    for(int j = 1;j <= 20;j ++) {
        for(int i = 1;i <= n;i ++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    int a,b;
    for(int i = 1;i <= m;i ++) {
        cin >> a >> b;
        int LCA = lca(a,b);
        diff[a] ++;
        diff[b] ++;
        diff[LCA] -= 2;
    }
    calculate(1,0);
    long long int total = 0;
    for(int i = 2;i <= n;i ++) {
        if(diff[i] == 0) {
            total += m;
        }else if(diff[i] == 1) {
            total ++;
        }
    }
    cout << total;
    for(int i = 1;i <= n;i ++) {
        edge *e = g[i].head;
        edge *tmp;
        while(e != nullptr) {
            tmp = e;
            e = e->next;
            delete tmp;
        }
    }
    return 0;
}

并查集

简介

并查集是一种用于管理元素所属集合的数据结构。实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

2种基本操作

Union 合并

合并两个元素所属集合（合并对应的树）

Find 查询

用于判断 2 个元素是否属于一个集合

实现

父亲存储法：只需要一个数组 f 存储每个节点的父亲即可。

查询：只要沿着树找到a, b所在树的根节点fa, fb，若fa, fb相等则两个节点在同一个集合中

合并：先沿着树找到a, b所在树的根节点fa, fb，再令f[fa] = fb, 将两树合并

并查集优化

降低树高

查询中的路径压缩

查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。
在从x到根结点的路径上的每一个结点都将自己的父结点改为根结点。

1
2
3
4
5
6
int find(x){
    if(parent[x] != x){
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

启发式合并

我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void unite(int x,int y){
    int rootX = find(x);
    int rootY = find(y);

    if(rootX == rootY){
        return;
    }

    if(size[rootX] < size[rootY]){
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    }else{
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
    }
}

生成树

连通图 G 的生成树（Spanning Tree）是包含G的所有节点的树。

在有权图中，**最小生成树（MST）**是指总权值最小的一棵生成树。

切割性质：假设将图中的顶点划分为两个互不相交的集合，那么连接这两个集合的所有边中，权重最小的边一定属于某棵最小生成树。

Kruskal 算法——求解MST （较为常用）

Core:对边排序，每次取出权值最小的边尝试加入，如果不成环则加入，直到全图连通。

Prim 算法——求解MST

从任意一个点开始，选距离集合最近的节点加入集合，直到全图连通

综合DS,MST和LCA

老规矩先贴题：货车运输
此题lz开始的想法是Floyd暴力dp，显然会炸。后来打算暴搜，显然也会炸。无奈只得点开luogu题解，发现是蓝题🤡
个人觉得最妙的是想到使用最大生成树，把较小的边删掉，在得到的最大生成树上（Kruskal得树，邻接表dfs建树）进行LCA操作，得到LCA后相当于求解出了唯一的一条路径，在遍历这条路径求个最小值就好了
另外lz总觉得最后的遍历有点儿暴力，感觉可以多维护一些东西，让查询复杂度来到O(1)？没仔细想，以为会T，结果居然1Y飘过了🤣
贴个代码：

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
using namespace std;
int parent[10005];
int Size[10005];
struct edge {
    int start;
    int end;
    int weight;
};
void merge(const edge *aBegin, const edge *aEnd, const edge *bBegin,
           const edge *bEnd, edge *c) {
    while (aBegin != aEnd && bBegin != bEnd) {
        if (bBegin->weight > aBegin->weight) {
            *c = *bBegin;
            ++bBegin;
        } else {
            *c = *aBegin;
            ++aBegin;
        }
        ++c;
    }
    for (; aBegin != aEnd; ++aBegin, ++c) *c = *aBegin;
    for (; bBegin != bEnd; ++bBegin, ++c) *c = *bBegin;
}
void merge_sort(edge *a, int l, int r) {
    if (r - l <= 1) return;
    int mid = l + ((r - l) >> 1);
    merge_sort(a, l, mid), merge_sort(a, mid, r);
    edge* tmp = new edge[r - l + 1];
    merge(a + l, a + mid, a + mid, a + r, tmp);
    for (int i = l; i < r; ++i) a[i] = tmp[i - l];
    delete []tmp;
}
int find(int u) {
    if(parent[u] != u) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}
void unite(int x,int y) {
    int rootX = find(x);
    int rootY = find(y);
    if(rootX != rootY) {
        if(Size[rootX] > Size[rootY]) {
            parent[rootY] = rootX;
            Size[rootX] += Size[rootY];
        }else {
            parent[rootX] = rootY;
            Size[rootY] += Size[rootX];
        }
    }
}
int n,m,q;
int u,v,w;
edge Graph[50005];
edge MST[10005];
struct adjEdge {
    adjEdge *next;
    int end;
    int weight;
};
struct adjVer {
    adjEdge *head;
};
adjVer adjMST[10005];//最大生成树邻接表
void add_edge(int u,int v,int w) {
    adjEdge *current = new adjEdge;
    current->end = v;
    current->weight = w;
    current->next = adjMST[u].head;
    adjMST[u].head = current;
}
int fa[10005][21];
int depth[10005];
void dfs(int sn,int f,int h) {
    fa[sn][0] = f;
    depth[sn] = h;
    adjEdge *current = adjMST[sn].head;
    while(current != nullptr) {
        if(current->end != f) {
            dfs(current->end,sn,h + 1);
        }
        current = current->next;
    }
}
int lca(int u,int v) {
    if(depth[u] < depth[v]) {
        swap(u,v);
    }
    for(int j = 20;j >= 0;j --) {
        if(depth[fa[u][j]] >= depth[v]) {
            u = fa[u][j];
        }
    }
    if(u == v) {
        return u;
    }
    for(int j = 20;j >= 0;j --) {
        if(fa[u][j] != fa[v][j]) {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}
int findVal(int u,int v) {
    adjEdge *current = adjMST[u].head;
    while(current != nullptr) {
        if(current->end == v) {
            return current->weight;
        }
        current = current->next;
    }
    return 0;
}
int getMin(int u,int lca) {
    int Min = 1e9;
    while(u != lca) {
        int v = findVal(u,fa[u][0]);
        if(v < Min) {
            Min = v;
        }
        u = fa[u][0];
    }
    return Min;
}
int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) {
        parent[i] = i;
        Size[i] = 1;
    }
    for(int i = 1;i <= m;i ++) {
        cin >> u >> v >> w;
        Graph[i].start = u;
        Graph[i].end = v;
        Graph[i].weight = w;
    }
    merge_sort(Graph,1,m + 1);
    int cnt = 0;
    for(int i = 1;i <= m;i ++) {
        int rst = find(Graph[i].start);
        int rnd = find(Graph[i].end);
        if(rst != rnd) {
            unite(rst,rnd);
            MST[++cnt] = Graph[i];
        }
    }
    for(int i = 1;i <= cnt;i ++) {
        add_edge(MST[i].start,MST[i].end,MST[i].weight);
        add_edge(MST[i].end,MST[i].start,MST[i].weight);
    }
    dfs(1,0,1);
    for(int j = 1;j <= 20;j ++) {
        for(int i = 1;i <= n;i ++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    cin >> q;
    int start,end;
    for(int i = 1;i <= q;i ++) {
        cin >> start >> end;
        if(find(start) != find(end)) {
            cout << -1 << '\n';
        }else {
            int LCA = lca(start,end);
            cout << min(getMin(start,LCA),getMin(end,LCA)) << '\n';
        }
    }
    return 0;
}
Algorithms
#Data Structure #Algorithm #LCA #Disjoint Set #MST #Kruskal #Prim
LCA DS MST
https://janezair.site/2025/05/11/AlgorithmOfDS4/
Author
Yihan Zhu
Posted on
May 11, 2025
Updated on
May 15, 2025
Licensed under