比较模版。

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=4e5+10;
bool v[N];vector<int>e[N];
int a[N],fa[N],x[N],y[N];
string s[N];int w[N],sz[N];
int findfa(int x)
{
	if(x==fa[x])return x;
	return fa[x]=findfa(fa[x]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,q;cin>>n>>m>>q;
	for(int i=1;i<=m;i++)cin>>x[i]>>y[i];
	for(int i=1;i<=q;i++)
	{
		cin>>s[i];
		if(s[i]=="DELETE")
		{
			cin>>w[i];
			v[w[i]]=1;
		}
	}
	for(int i=1;i<=n;i++)cin>>a[i],sz[i]=a[i];
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)if(!v[i])
	{
		int tx=findfa(x[i]),ty=findfa(y[i]);
		if(tx==ty)continue;
		if(tx<ty)swap(tx,ty);
		fa[tx]=ty;sz[ty]+=sz[tx];
	}
	int lgc=q+1,ans=sz[1]*lgc;
	for(int i=q;i>=1;i--)
	{
		if(s[i]=="GC")lgc=i;
		else
		{
			int xx=x[w[i]],yy=y[w[i]];
			int tx=findfa(xx),ty=findfa(yy);
			if(tx==ty)continue;
			if(tx<ty)swap(tx,ty);
			fa[tx]=ty;sz[ty]+=sz[tx];
			if(ty==1)ans+=lgc*sz[tx];
		}
	}
	for(int i=1;i<=n;i++)
		if(findfa(i)!=1)ans+=lgc*a[i];
	cout<<ans;return 0;
}

题意：

给定一个五香无向图。

每个节点 $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;
}