Luogu P6185 [NOI Online #1 提高组]序列

小 D 有一个长度为 n 的整数序列 a_{1 \dots n}，她想通过若干次操作把它变成序列 b_i。

小 D 有 m 种可选的操作，第 i种操作可使用三元组 (t_i,u_i,v_i)描述：若t_i=1，则她可以使 a_{u_i} 与a_{v_i}都加一或都减一；若t_i=2，则她可以使 a_{u_i} 减一、a_{v_i} 加一，或是 a_{u_i} 加一、a_{v_i} 减一，因此当 u_i=v_i 时，这种操作相当于没有操作。

小 D 可以以任意顺序执行操作，且每种操作都可进行无限次。现在给定序列与所有操作，请你帮她判断是否存在一种方案能将 a_i 变为b_i。题目保证两个序列长度都为 n。若方案存在请输出 YES，否则输出 NO。

我们可以把每个数字当作一个点，t=2了话将u和v连起来。

如图所示，发现在一个连通块的点可以任意加减，但是连通块总和不变。

（虽然1和3没有直接连接，但是2使他们处于同一联通块，所以间接等于直接连了起来。）

我们所以把一个连通块缩成一个点就好。

然后看操作1

缩点后的操作1相当于可以将2个连通块同时加减，然后传递一下就会发现，可以实现操作2

如果缩点后的图是二分图

那么可以左部和右部内部之间 可以借助两部之间的操作1，来完成内部之间的操作2。

那么现在相当于只剩下左部和右部两个点了，只用保证左部之和等于右部，就可以通过操作1达到题目要求

如果不是二分图

考虑原二分图内部之间有连接，可以执行操作1，借助二分图左右两边的操作1，可以实现内部任一点的操作1。

也就是内部两点可以同时加1或者减1，等效于左部或右部加2或减2，执行无数次就是内部可以加减任意偶数，而且此时仍具有前面二分图的性质

于是只用保证左右两边奇偶性相同，便可以达到题目要求。

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+10;
std::vector<int> G[N];
int fa[N];
ll a[N],b[N],c[N],                                                                                                                                                                                        v[N];
int n,m;
ll s[10];
int p[N],q[N],tot;
int get(int x){
    if(!fa[x]) return x;
    return fa[x]=get(fa[x]);
}
int dfs(int x,int k){
    int S=G[x].size();
    v[x]=k;
    s[k]+=c[x];
    int fl=1;
    for(int i=0;i<S;++i){
        int vv=G[x][i];
        if(v[vv]==v[x]){
            fl=0;
        }
        else
            if(!v[vv])
                fl&=dfs(vv,3-k);
    }
    return fl;
} 
int main(){
//  freopen("da.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        memset(fa,0,sizeof(fa));
        memset(v,0,sizeof(v));
        memset(c,0,sizeof(c));
        tot=0;
        for(int i=1;i<=n;++i){
            G[i].clear();
        }
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;++i){
            scanf("%lld",&b[i]);
        }

        for(int i=1;i<=m;++i){
            int t,u,v;
            scanf("%d %d %d",&t,&u,&v);
            if(t==1){
                tot++;
                p[tot]=u;
                q[tot]=v;
            }
            else{
                u=get(u),v=get(v);
                if(u!=v)
                    fa[u]=v;
            }
        }
        for(int i=1;i<=n;++i)
            c[get(i)]+=a[i]-b[i];
        for(int i=1;i<=tot;++i){
            int u=get(p[i]);
            int v=get(q[i]);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int ok=1;
        for(int i=1;i<=n;++i){
            if(i==get(i)&&!v[i]){
                s[1]=s[2]=0;
                int fl=dfs(i,1);
                if(fl){
                    if(s[1]!=s[2])
                        ok=0;
                }
                else{
                    if((s[1]+s[2])&1)
                        ok=0;
                }
            }
        }
        if(ok) puts("YES");
        else puts("NO");
    }
    return 0;
}