SS241006B. 结论题

题意

给你一个无向图，每个点有点权 \(1 \le a_i \le 10^6\) 和颜色 \(c_i=0/1\)。可以进行若干次操作：选择任意一条边，交换两个点的点权，如果两个点的颜色相同，两个点的颜色分别取反。给出初始状态和一个终态，判断是否存在到达终态的方案。

思路

真结论题。

这个操作非常恶心。巧妙地转化一下可以变成每次选定一条边，交换点权和颜色，然后对颜色取反。然后我们发现这个操作是可逆的。

考虑二分图怎么做。

首先原图可以分成若干个连通块分别做。

对于一个连通块，因为它是连通的，类似冒泡排序，所以点权是可以任意排序的，但是颜色还有取反操作。

对于二分图，一个左部的点如果换到了左部，颜色不变，换到了右部，颜色取反。

所以对于每个点，我们记录一个二元组 \((点权，点在左部时的颜色)\)，对初态和终态都做这样的记录。如果初态和终态的元素相同，就一定有可行方案。对于初态的某个二元组和终态的某个二元组的一对匹配，如果在终态的原图，这个二元组在右部，那么初态的那个二元组也移到右部对应位置就行，这是可以一一匹配的。因为这是一个连通块，所以可以任意排序，因此结论成立。

对于非二分图的情况。结论是，初态点权和终态点权集合相同，且初态原图颜色 \(0\) 和终态原图颜色 \(0\) 的个数奇偶性相同（\(1\) 也一样）。必要性显然。下面证明其充分性。

首先我们在原图随便找一个生成二分图，比如找一个生成树。然后对每个点维护上面提到的二元组 \((点权，点在左部时的颜色)\)。由上面的结论可以知道，如果初态的二元组集合和终态相同，就一定有可行的方案。也就是说，在这个二分图上面我们可以任意排序这些二元组同时不改变它们的值。

原图就是二分图上加上了若干条边，如果在不同部加边（生成树奇数层和偶数层连边），图还是一个二分图，没有新的性质。如果在生成树奇数和奇数（或偶数和偶数）层连边，就出现了奇环。

类似冒泡排序，在这个奇环上所有点的点权可以任意排序，其实不需要再奇环上面排序，如果在二分图的路径上，不仅也可以任意排序，而且二元组的 \(点在左部的颜色\) 这个值还不会改变。现在证明之前那个结论的充分性。我们可以通过二分图上的路径把两个颜色相同的点放到非二分图的那条边的两个端点，然后交换它们，并取反颜色，这样某个颜色的总数就会 \(-2\) 了。而且我们只需要一个奇环，因为你可以把整棵生成树的点任意排序，把你想要改变颜色的点颜色取反。因此利用某一个奇环做若干次颜色取反，就可以使初态和终态二元组的集合相同了，然后由于二分图可以任意排序二元组，所以结论充分。

证毕。

code

#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1e5+7;
template <typename T>
inline void read(T &x) {
	x=0;
	T fl=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') fl=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	x=x*fl;
}
template <typename T>
inline void write(T x,char ch) {
	static int st[10];
	int top=0;
	if(x<0) putchar('-'),x=-x;
	do {
		st[top++]=x%10;
		x/=10;
	}while(x);
	while(top) putchar(st[--top]+'0');
	putchar(ch);
}
int T,n,m;
vector<int> to[N];
int vi[N];
int u,v;
char ch[N];
typedef pair<int,int> pii;
#define fi first
#define se second
pii s[N],t[N];
bool checkeft(int &cs,int &ct,vector<pii> &vecs,vector<pii> &vect,int u) {
	bool ans=1;
	if(s[u].se) cs++;
	if(t[u].se) ct++;
	if(vi[u]==2) s[u].se^=1,t[u].se^=1;
	vecs.push_back(s[u]);vect.push_back(t[u]);
	for(int v:to[u]) {
		if(!vi[v]) vi[v]=(vi[u]==1?2:1),ans&=checkeft(cs,ct,vecs,vect,v);
		else if(vi[u]==vi[v]) ans=0;
	}
	return ans;
}
int main() {
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#else
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	#endif
	read(T);
	while(T--) {
		read(n),read(m);
		rep(i,1,m) {
			read(u),read(v);
			to[u].push_back(v),to[v].push_back(u);
		}
		rep(i,1,n) read(s[i].fi);
		sf("%s",ch+1);
		rep(i,1,n) s[i].se=(ch[i]=='R'?1:0);
		rep(i,1,n) read(t[i].fi);
		sf("%s",ch+1);
		rep(i,1,n) t[i].se=(ch[i]=='R'?1:0);
		bool ans=1;
		rep(k,1,n) {
			if(!ans) break;
			if(vi[k]) continue;
			vector<pii> vecs,vect;
			int cnts=0,cntt=0;
			vi[k]=1;
			bool check=checkeft(cnts,cntt,vecs,vect,k);
			sort(vecs.begin(),vecs.end());
			sort(vect.begin(),vect.end());
			if(check) {
				rep(i,0,(int)vecs.size()-1) {
					if(vecs[i]!=vect[i]) {
						ans=0;
						break;
					}
				}
			}else{
				if((cnts&1)!=(cntt&1)) ans=0;
				rep(i,0,(int)vecs.size()-1) {
					if(vecs[i].fi!=vect[i].fi) {
						ans=0;
						break;
					}
				}
			}
		}
		if(ans) pf("YES\n");
		else pf("NO\n");
		rep(i,1,n) to[i].clear(),vi[i]=0;
	}
}