25pts 求帮助
查看原帖
25pts 求帮助
476574
KAWorld楼主2023/7/11 11:50
#include<bits/stdc++.h>
#define MAXN 400005
using namespace std;
inline int read(){
	int m=0,t;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if (c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		m=m*10+c-'0';c=getchar();
	}
	return m;
}
inline long long llread(){
	long long m=0,t;
	char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if (c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		m=m*10+c-'0';c=getchar();
	}
	return m;
}
inline void write(long long n){
	if(n<10){
		putchar(n+'0');return;
	}
	write(n/10);
	putchar(n%10+'0');
}
int x[MAXN],y[MAXN],e[MAXN],fa[MAXN];
long long s[MAXN];
bool f[MAXN];
char ch[10];
inline int getfa(int p)
{
	return p==fa[p]?p:fa[p]=getfa(fa[p]);
}
int main(){
	unsigned long long ans=0;
	int n,m,q,tot=1;
	n=read();m=read();q=read();
	for(register int i=1;i<=m;++i){
		x[i]=read();y[i]=read();
	}
	for(register int i=1;i<=q;++i){
		cin>>ch;
		if(ch[0]=='D'){
			int x=read();f[x]=!f[x];e[i]=x;
		}
		else e[i]=0;
	}
	for(register int i=1;i<=n;++i){
		s[i]=llread();fa[i]=i;
	}
	for(register int i=1;i<=m;++i)
		if(!f[i]){
			int fx=getfa(x[i]),fy=getfa(y[i]);
			if(fy==1){
				fa[fx]=fy;s[fy]+=s[fx];
			}
			else{
				fa[fy]=fx;s[fx]+=s[fy];
			}
		}
	for(register int i=q;i>=1;--i){
		if(!e[i]){
			ans+=s[1]*tot;tot=0;
		}
		else{
			int fx=getfa(x[e[i]]),fy=getfa(y[e[i]]);
			if(fx!=fy)
				if(fy==1){
					fa[fx]=fy;s[fy]+=s[fx];
				}
				else{
					fa[fy]=fx;s[fx]+=s[fy];
				}
		}
		++tot;
	}
	ans+=s[1]*tot;
	memset(f,0,sizeof(f));
	for(register int i=1;i<=n;++i){
		fa[i]=getfa(fa[i]);
		if(fa[i]!=1&&!f[fa[i]]){
			ans+=s[fa[i]]*tot;f[fa[i]]=!f[fa[i]];
		}
	}
	write(ans);
	return 0;
}
2023/7/11 11:50
加载中...