题解 - 题解&笔记 - 颜色限制（restriction）& （树上）启发式合并
有一个 $n$ 点 $m$ 边的无向图，有 $k$ 种颜色编号为 $0∼k−1$，每条边有一种颜色... | 难度：普及
颜色限制（restriction）
时间限制: 1000ms 空间限制: 524288kB 输入文件名:
restriction.in输出文件名:restriction.out
题目描述
有一个 $n$ 点 $m$ 边的无向图，有 $k$ 种颜色编号为 $0∼k−1$，每条边有一种颜色。对于每种颜色，请判断假如删去所有这种颜色的边，得到的图是否连通？是否是一棵树？
输入格式
从文件 restriction.in 中读入。
第一行三个整数 $n,m,k$ ，表示点数、边数、颜色数。接下来 $m$ 行，每行三个整数 $u,v,c$ ，表示一条无向边$(u,v)$ 的颜色为 $c$。
输出格式
输出到文件 restriction.out 中。
一行两个整数 $p,q$ ，表示满足删去后图连通的颜色数和删去后图是树的颜色数。
样例
Input 1
1
2
3
4
5
6
5 5 4
1 2 0
2 3 0
3 4 1
4 5 2
5 2 3
Output 1
1
3 3
Input 2
1
2
3
4
5
6
5 5 2
1 2 0
2 3 0
3 4 0
4 5 0
5 2 0
Output 2
1
1 0
数据范围
对于全部数据：$1\le n,m\le 10^5$，$2\le k\le 10^5$，$1\le u \neq v\le n$，$0\le c < k$。 图无自环，但可能有重边。
| 子任务 | $n\le$ | $m\le$ | $k\le$ | 所有颜色相等 | 分值 |
|---|---|---|---|---|---|
| $1$ | $300$ | $300$ | $300$ | 否 | $10$ |
| $2$ | $10^3$ | $10^5$ | $10^3$ | 否 | $30$ |
| $3$ | $10^5$ | $10^5$ | $2$ | 否 | $10$ |
| $4$ | $10^5$ | $10^5$ | $10^5$ | 是 | $10$ |
| $5$ | $10^5$ | $10^5$ | $10^5$ | 否 | $40$ |
样例解释
样例 1 解释
除了颜色 $0$ 以外，其他颜色删去后均得到树，而删去$0$ 图不连通。
题目分析
题面还是比较简单的，就是有各种颜色的边，问仅去掉一个边，图是否连通，是否为树。
先来看第二个小问。
问一个图 $G\lang E, V \rang$ 是否为树，我们只要判断 $\lbrack V = E - 1\rbrack$ 即可，做一个统计，复杂度 $\mathcal{O}(m + k)$ 。
再看第一小问。
数据范围很大，每次遍历减去某个颜色的边绝对不行。我们先将颜色编号指向该颜色的边。 一开始想到，映射完毕之后可以将这些颜色加入到并查集，然后每次枚举去掉一个点之后的并查集，看是否连通。但是这样时间复杂度还是很高，为$\mathcal{O}(k(m + n))$。
所以我们就要介绍一种并查集的写法：
并查集启发式合并
启发式合并放弃了路径压缩，但是它尽可能地将这棵树压缩到最小。 很明显，我们根据树的大小或者深度合并，是最经济的做法。对于大部分可持久化算法，根据树的大小合并会节省一些空间。
具体做法：
开一个 $cnt$ 数组，记录并查集的大小，初始化为1。在每次合并的时候，都将 $cnt$ 小的一方合并到 $cnt$ 大的一方。
并查集撤销
- 对于启发式并查集，如果我们知道合并顺序，其实可以开一个栈，正序合并，逆序拆解，具体可以看本题代码。
- 对于单点撤销，考虑别的做法。
- 初始化的时候，维护一个数据范围之外的 $cnt$，在删除的时候，将删除的点的父亲挂载为 $cnt$ ，并将 $cnt$ 的父亲挂为 $cnt$ 自己，$cnt++$。
扩展：树上启发式合并
做法讲解：
-
遍历每一个节点
-
递归解决所有的轻儿子，同时消除递归产生的影响
-
递归重儿子，不消除递归的影响
-
统计所有轻儿子对答案的影响
-
更新该节点的答案
-
删除所有轻儿子对答案的影响
例题（更新）
我们继续看本题。思路其实跟树上问题类似，都是要利用重链部分对解进行计算。 考虑分治。设 $solve(l,r)$ 表示解决删去的颜色在 $[l,r]$ 时的问题。先将颜色在 $[l,mid]$ 的边加到图中，递归 $solve(mid+1,r)$ 即可求得删去的颜色在 $[mid+1,r]$ 的所有答案；同理可以求得删去的颜色在 $[l,mid]$ 的所有答案。使用可撤销并查集维护连通性即可。
AC Code
time: 806ms, memory: 9552kb, score: 100, status: Accepted 本题卡快读
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 100;
struct edge{int from, to;};
int fa[MAXN];
int cnt[MAXN];
int n, m, k;
vector<edge> G[100010];
inline void init() {
for(int i = 1; i <= n; i++) {
fa[i] = i, cnt[i] = 1;
}
}
inline int read() {
char ch = getchar(); int x = 0, f = 1;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
return x;
}
int find(int pos) {
return fa[pos] == pos ? pos : find(fa[pos]);
}
int ans1 = 0, ans2 = 0;
void dfs(int l, int r) {//访问到这里，应该是提前被删除或者没有加的
if(l == r) {
if(cnt[find(1)] == n) {
ans1++;
if(m - (int)G[l].size() == n - 1) ans2++;
}
return;
}
int mid = (l + r) >> 1;
stack<pair<int, int>> st;
for(int i = l; i <= mid; i++) {
for(auto j : G[i]) {
int u = find(j.from), v = find(j.to);
if(u != v) {
if(cnt[u] < cnt[v]) swap(u, v);
st.emplace(u, v);
fa[v] = u, cnt[u] += cnt[v];
}
}
}
dfs(mid + 1, r);
while(!st.empty()) {
auto t = st.top(); st.pop();
fa[t.second] = t.second;
cnt[t.first] -= cnt[t.second];
}
for(int i = mid + 1; i <= r; i++) {
for(auto j : G[i]) {
int u = find(j.from), v = find(j.to);
if(u != v) {
if(cnt[u] < cnt[v]) swap(u, v);
st.emplace(u, v);
fa[v] = u, cnt[u] += cnt[v];
}
}
}
dfs(l, mid);
while(!st.empty()) {
auto t = st.top(); st.pop();
fa[t.second] = t.second;
cnt[t.first] -= cnt[t.second];
}
}
int main()
{
freopen("restriction.in", "r", stdin);
// freopen("restriction.out", "w", stdout);
n = read(), m = read(), k = read();
init();
int u, v, c;
for(int i = 1; i <= m; i++) {
u = read(), v = read(), c = read();
edge E;
E.from = u, E.to = v;
G[c].emplace_back(E);
}
dfs(0, k - 1);
printf("%d %d\n", ans1, ans2);
return 0;
}