自动搬运

查看原文

来自洛谷，原作者为

	LXYYDS HEY, MAN, 我是只马蜂

搬运于2025-08-24 22:38:23，当前版本为作者最后更新于2022-07-01 00:16:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

给定一个五香无向图。

每个节点 $i$ 有两种属性 $a_i$ 以及 $alive_i$。

其中 $a_i$ 题目中给出， $alive_i$ 初始值为 $0$。

对五香图进行以下两种操作：

1. 删除一条边。

2. 对于每个 $^{1.}$ 与起点（编号为 $1$ 的节点）不连通， $^{2.} alive$ 值为 $0$ 的点 $i$ ，将 $alive_i$ 的值改为当前时间戳（当前操作的编号）

共 $q$ 种操作，编号为 $1 \to q$。

所有操作执行完后，将剩余的 $alive$ 值为 $0$ 的点的 $alive$ 改为 $q + 1$。 求：

暴力

显然我们有暴力做法：

对于每条边额外记录一个类型为 bool 的值，表示这条边的状态（ $0$ 表示未删除， $1$ 表示已删除）。

经过上述变换后，可以拿一半的分数。物美价廉，岂不美哉！

正解

对于暴力做法，我们将删边时间变为 $O(1)$ ，改值时间则为 $O(n)$。

由此可见，改值操作时间过长，所以，我们希望优化。

观察数据范围可知，本题时间复杂度应为 $O(n \cdot \log_2n)$ 或 $O(n)$。

感性理解，应为数据结构。

此时我们要有 逆向思维 。

删边 等价于 加边。

于是就有思路了：

我们将操作 $1$（删边）反向，改为加边。

那么处理加边的数据结构有哪些呢？并查集！

我们将上面的零散的思路组合一下，这道题的解法就出来了！

简略完整思路如下：

1. 将所有没有删去的边保留下来，建立初始并查集。

2. 倒序处理所有操作，对于删边操作，改为加边（用并查集维护），额外记录每个点所在并查集的 $a_i$ 的总和 $s_i$ ，对于一次合并，若两个集合有且仅有一个集合包含起点，则 $ans+=s_i \cdot time$ 其中， $time$ 表示时间戳，初值为 $q + 1$。

3. 对于改值操作，修改时间戳。

一些细节：

1. 图有可能本来就不连通（如样例 $2$ )操作之后还需要将剩下的点再做处理。

2. $ans$ 需要 unsigned long long ！！！

代码

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;



struct Edge {
	long long x, y, d;
	bool b;
};
string S[400009];
Edge e[400009]; 
long long n, m, q, dele[400009], father[400009], cnt;
bool visit[400009];
unsigned long long ans, tim, ln, siz[400009], yua[400009];

long long get_father(long long x) {
	return x == father[x] ? x : father[x] = get_father(father[x]);
}




int main () {
	scanf("%lld%lld%lld", &n, &m, &q);
	for (register long long i = 1; i <= m; i ++) {
		scanf("%lld%lld", &e[i].x, &e[i].y);
		e[i].d = i;
		e[i].b = true;
	}
	
	for (register long long i = 1; i <= n; i ++) {
		if (visit[i])
			continue;
		ln += siz[i];
	}
	for (register long long i = 1; i <= q; i ++) {
		cin >> S[i];
		if (S[i] == "DELETE") {
			cin >> dele[i];
			e[dele[i]].b = false;
		}	
	}
	for (register long long i = 1; i <= n; i ++) {
		cin >> siz[i];
		yua[i] = siz[i];
	}
		
	for (register long long i = 1; i <= n; i ++) {
		father[i] = i;
	}
	for (register long long i = 1; i <= m; i ++) {
		if (e[i].b) {
			long long x = get_father(e[i].x), y = get_father(e[i].y);
			if (x == y)
				continue;
			if (x == 1) {
				siz[x] += siz[y];
				father[y] = x;
			}
			else {
				siz[y] += siz[x];
				father[x] = y;
			}
		}
	}
	tim = q + 1;
	ans = tim * siz[1];
	for (register long long i = q; i >= 1; i --) {
		if (S[i] == "GC") {
			tim = i;
		}
		else {
			long long x = get_father(e[dele[i]].x), y = get_father(e[dele[i]].y);
			if (x == y)
				continue;
			if (x == 1) {
				siz[x] += siz[y];
				ans += tim * siz[y];
				father[y] = x;
			}
			else if (y == 1) {
				siz[y] += siz[x];
				ans += tim * siz[x];
				father[x] = y;
			}
			else {
				siz[y] += siz[x];
				father[x] = y;
			}
			
		}
	}
	for (register long long i = 1; i <= n; i ++)
		if (get_father(i) != 1)
			ln += yua[i];
	printf("%llu\n", ans + tim * ln);
	return 0;
}