NOI ONLINE 提高组 序列

题目描述

小 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$ 表示数据组数。对于每组数据：

第一行两个整数 $n,m$，表示序列长度与操作种数。

第二行 $n$ 个整数表示序列 $a_i$。

第三行 $n$ 个整数表示序列 $b_i$。

接下来 $m$ 行每行三个整数 $t_i,u_i,v_i$，第 $i$ 行描述操作 $i$。

注意：同一个三元组 $(t_i,u_i,v_i)$ 可能在输入中出现多次。

输出格式

对于每组数据输出一行一个字符串 YES 或 NO 表示答案。

样例输入

3
1 1
1
3
1 1 1
2 3
1 2
4 5
1 1 2
2 1 2
1 1 2
3 3
1 2 3
5 5 4
1 1 2
1 1 3
2 2 3

样例输出

YES
YES
YES

提示

第一组数据：使用一次操作 $1$。
第二组数据：使用三次操作 $1$。
第三组数据：使用三次操作 $1$，令 $a_1,a_2$ 都增加 $3$，再使用一次操作 $2$，令 $a_1,a_3$ 都增加 $1$。

数据范围

对于测试点 $1 \sim 5$：$n=2$，$m=1$，$a_i,b_i \le 99$，$u_1 \ne v_1$，$t_1=1$。
对于测试点 $6 \sim 10$：$n=2$，$m=1$，$a_i,b_i \le 99$，$u_1 \ne v_1$，$t_1=2$。
对于测试点 $11 \sim 12$：$n=2$，$a_i,b_i \le 99$，$u_i \ne v_i$。
对于测试点 $13 \sim 16$：$t_i=2$。
对于测试点 $17$：$n,m \le 20$。
对于测试点 $18$：$n,m \le 10^3$。
对于所有测试点：$1 \le T \le 10$，$1 \le n,m \le 10^5$，$1 \le a_i,b_i \le 10^9$，$t_i \in \{1,2\}$，$1\le u_i,v_i \le n$。

分析

说实话第一眼看到这题的时候我有点懵，真不知道怎么做，不过一看数据，还好还好，暴力能拿一半分，于是我就真拿了一半分。。。。。

但某大佬说暴力能拿60，但我拿一半就满意了 我不会啊

考完后忍不住好奇这道题要怎么做，于是就看了看题解，发现题解也。。。有点难懂，主要是我看到一个字，图？？这明明是个数的问题咋还和图扯上了关系，awsl，果然还是我太菜了

仔细读了一下，明白了一些。先看操作一：如果有(a1,a2)(a2,a3)(a3,a1),那么其中任意一个数都能自己加减二，如a1，a1+1,a2+1,a2-1,a3-1,a3+1,a1+1这样就能让a1自己加减二，同理a1换成任何数都可以，这里要注意，必须是奇数个点并且形成环才能这样办，所以每个奇数环上的数都能加减二，偶数个点为什么不行自己举个例子就明白了。再看操作二：如果有(a1,a2)(a2,a3)那么可以知道(a1,a3)，a1+1,a2-1,a2+1,a3-1由此,a1+1，a3-1，可见操作二是具有传递性的，如果把它们看做是一个联通块，那么这个联通块可以任意加1，减1，所以如果这个联通块需要加的值和需要减的值一样，那么就满足。于是我们只要把每个操作二都缩成点，每个操作一建边，然后开始判断每块联通块是不是满足题意。

判断方法为，如果未形成奇数环，则需要使联通块内相加的数与相减的数相等，因为只能加一减一，否则使需要变化的总数是偶数即可，注意自环也要判断，因为自环相当于(a1,a2,1)(a1,a2,2)即a1+1,a2+1,a2-1,a1+1,这样也能使任意数加减二，

然后还有就是对于没有边连入的点，只有需要变化的值为0，才满足，因为没有边可以使它产生变化。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
long long val[N];
struct Edge{
    int to,next;
}e[N];
struct Node{
    int t,u,v;
}p[N];
int Head[N],len,sum,flag;
void Ins(int a,int b){
    e[++len].to=b;e[len].next=Head[a];Head[a]=len;
}
int f[N],belong[N],a[N],b[N];
int find(int x){
    return f[x]==x?x:(f[x]=find(f[x]));
}
void Mer(int a,int b){
    int u=find(a),v=find(b);
    if(u!=v){
        f[u]=v;val[v]+=val[u];//并查集缩点
    }
}
void dfs(int x,int bin){
    belong[x]=bin;
    if(bin)sum+=val[x];
    else sum-=val[x];
    for(int i=Head[x];i;i=e[i].next){
        int v=e[i].to;
        if(belong[v]==-1)dfs(v,bin^1);//利用了^的性质
        else if(belong[x]==belong[v])//说明v已经被提前访问过并且bin的值与x一样，那么就一定形成了奇数环
            flag=1;
    }
}
int main(){
//    freopen("a.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int m,n,ans=1;len=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]),val[i]=b[i]-a[i];
        for(int i=1;i<=n;i++)
            f[i]=i,belong[i]=-1,Head[i]=0;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&p[i].t,&p[i].u,&p[i].v);
            if(p[i].t==2){
                Mer(p[i].u,p[i].v);//合并操作二
            }
        }
        for(int i=1;i<=m;i++){
            if(p[i].t==1){
                Ins(find(p[i].u),find(p[i].v));//这里已经缩点所以要合并根
                Ins(find(p[i].v),find(p[i].u));
            }
        }
        for(int i=1;i<=n;i++){
            if(find(i)==i&&belong[i]==-1){
                flag=sum=0;
                dfs(i,0);
                for(int x=Head[i];x;x=e[x].next){
                    if(e[x].to==i)flag=1;//自环
                }
                if(Head[i]==0&&sum!=0)ans=0;//没有边连入
                else if(flag==1&&sum%2!=0)ans=0;//奇数环
                else if(flag==0&&sum!=0)ans=0;//偶数环
            }
        }
        if(ans)printf("YES\n");
        else printf("NO\n");
    }
}