题解 P6185 [NOI Online 提高组]序列（民间数据）
xukuan
2020-03-11 23:06:16
首先我们发现，如果不同的数字之间有2操作连接，那么在保证他们总和不变的情况下可以任意分配里面的值。
所以我们可以把所有的相连的并到一起。
然后1操作不改变原来的数字差。这个时候重新按1操作连边，然后黑白染色。如果可以黑白染色就说明同种颜色的点的和的奇偶性不变的情况下操作，如果不能就说明可以在总和奇偶性不变的情况下操作
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=100010;
ll n,m,a[N],b[N],father[N],colour[N],cost[2],sum[N];
ll ver[N<<1],Next[N<<1],head[N],tot;
struct node{
ll t,x,y;
}E[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void addEdge(ll x,ll y){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
ll searchfather(ll v){
return father[v]==v?father[v]:father[v]=searchfather(father[v]);
}
bool dfs(ll x,ll op){
colour[x]=op; cost[op]+=sum[x];
bool flag=1;
for(ll i=head[x]; i; i=Next[i]){
ll y=ver[i];
if(colour[x]==colour[y]) flag=0;
if(colour[y]==-1&&!dfs(y,1-op)) flag=0;
}
return flag;
}
inline bool check(){
memset(colour,-1,sizeof(colour));
for(ll i=1; i<=n; i++){
if(searchfather(i)==i&&colour[i]==-1){
cost[0]=cost[1]=0;
bool flag=dfs(i,0);
if(flag&&cost[0]!=cost[1]) return 0;
if(!flag&&(cost[0]^cost[1])&1) return 0;
}
}
return 1;
}
inline bool cmp(node a,node b){
return a.t>b.t;
}
inline bool clean(){
memset(sum,0,sizeof(sum));
memset(ver,0,sizeof(ver));
memset(Next,0,sizeof(Next));
memset(head,0,sizeof(head));
tot=0;
memset(E,0,sizeof(E));
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
for(ll T=read(); T; T--){
clean();
n=read(); m=read();
for(ll i=1; i<=n; i++) a[i]=read();
for(ll i=1; i<=n; i++) b[i]=read();
for(ll i=1; i<=n; i++) father[i]=i;
for(ll i=1; i<=m; i++){
E[i].t=read(); E[i].x=read(); E[i].y=read();
}
sort(E+1,E+1+m,cmp);
for(ll i=1; E[i].t==2; i++){
ll f1=searchfather(E[i].x),f2=searchfather(E[i].y);
if(father[f1]!=f2) father[f1]=f2;
}
for(ll i=1; i<=n; i++) sum[searchfather(i)]+=b[i]-a[i];
for(ll i=m; E[i].t==1; i--){
ll x=searchfather(E[i].x),y=searchfather(E[i].y);
addEdge(x,y);
addEdge(y,x);
}
if(check()) printf("YES\n");
else printf("NO\n");
}
fclose(stdin); fclose(stdout);
return 0;
}
```