80pts求调
查看原帖
80pts求调
1003108
RainWetPeopleStart楼主2024/7/22 21:58
#include<bits/stdc++.h>
#define int long long
#define jp8 push_back
using namespace std;
const int N=1e5+10;
vector<int> e[N];
int dt[N];
bool tcd[N];
int fa[N];
int vla[N],vlb[N],bel[N],siz[N];
int n,m;
struct nd{
	int a,b;
}inst[N];
int A[N],B[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}void merge(int a,int b){
	if(find(a)==find(b)) return ;
	fa[a]=b;
}bool vis[N];int clr[N];
bool res[N],block;
int bel2[N];
void dfs(int u,int cl){
	vis[u]=1;
	clr[u]=cl;bel2[u]=block;
	siz[block]++;
	for(auto v:e[u]){
		if(clr[v]==clr[u]) res[block]=0;
		if(vis[v]) continue;
		dfs(v,1-cl);
	}
}int sum1[N][2],sum2[N][2];
void slv(){
	cin>>n>>m;
	int leni=0; 
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<=n;i++) cin>>B[i];
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int op,u,v;cin>>op>>u>>v;
		if(op==1) inst[++leni]=(nd){u,v};
		else merge(u,v);
	}memset(tcd,0,sizeof(tcd));int lend=0;
	memset(vla,0,sizeof(vla));
	memset(vlb,0,sizeof(vlb));
	for(int i=1;i<=n;i++){
		if(!tcd[find(i)]) ++lend,dt[find(i)]=lend,tcd[find(i)]=1;
		bel[i]=dt[find(i)];
		vla[bel[i]]+=A[i],vlb[bel[i]]+=B[i];
	}for(int i=1;i<=n;i++) e[i].clear();
	//cout<<leni;
	for(int i=1;i<=leni;i++){
		e[bel[inst[i].a]].jp8(bel[inst[i].b]);
		e[bel[inst[i].b]].jp8(bel[inst[i].a]);
		//if(i==1) cout<<bel[inst[i].a]<<' '<<bel[inst[i].b];
	}memset(vis,0,sizeof(vis));
	for(int i=1;i<=lend;i++) clr[i]=-1;
	block=0;
	for(int i=1;i<=lend;i++) res[i]=1,sum1[i][0]=0,sum1[i][1]=0,sum2[i][0]=0,sum2[i][1]=0,siz[i]=0; 
	for(int i=1;i<=lend;i++){
		if(vis[i]) continue;
		++block;dfs(i,0);
	}for(int i=1;i<=lend;i++){
		if(!res[bel2[i]]){
			sum1[bel2[i]][0]+=vla[i];
			sum1[bel2[i]][1]+=vlb[i];
		}else{
			if(clr[i]==0){
				sum1[bel2[i]][0]+=vla[i];
				sum1[bel2[i]][1]+=vlb[i];
			}else{
				sum2[bel2[i]][0]+=vla[i];
				sum2[bel2[i]][1]+=vlb[i];
			}
		}
	}for(int i=1;i<=block;i++){
		if(res[i]){
			if(sum1[i][0]-sum1[i][1]!=sum2[i][0]-sum2[i][1]){
				cout<<"NO"<<endl;
				return ;
			}
		}else{
			if(abs(sum1[i][0]-sum1[i][1])%2!=0){
				cout<<"NO"<<endl;
				return ;
			}
		}
	}cout<<"YES"<<endl;
}
signed main(){
	int t;cin>>t;
	while(t--) slv();
	return 0;
}
2024/7/22 21:58
加载中...