[Public NOIP Round #3]图同构

点权和颜色的操作不对称，尝试转化为同类操作。

对于颜色的操作可以看作：交换两点颜色，然后反色

那么可以将颜色和点权绑在一起交换，最终颜色是否反色取决于路径长度的奇偶性。

根据部分分的提示，分别考虑两种连通块

1. 不含奇环(二分图)

注意到此时路径的奇偶性等同于起点终点是否在同一部。

那么对于一种点权，可以还原的必要条件是A,B图中左部的R点与右部的B点的点数和相同，左部的B点与右部的R点的点数和相同

通过构造可以证明它的充分性：

任取这个连通块的一棵生成树，任取一个叶子，不妨设其在 B 图中为左部黑点或右部红点，则任取 A 图中一个点权相同的左部黑点或右部红点（由和相等一定存在），将其一路交换过来，以后的过程就可以在两张图中都忽略这个叶子。最后所有点都可以归位。

2. 含奇环

注意到经过的边数之和为偶数。

那么可以还原的必要条件是两图黑点奇偶性相同，红点奇偶性相同，且两图每种点权的点数相等。

通过构造可以证明它的充分性：

连通块本身为奇环，可以考虑点权不变的情况下反转相邻两点颜色。（不改变颜色的奇偶性）

• 将 \(x\) 上的二元组沿反方向交换一圈到 \(y\) 点，然后将原本 \(y\) 上的二元组沿反方向交换一圈到 \(x\) 点。

那么先将点权归位，再修改颜色即可完成构造

若连通块不为奇环，任取这个连通块的一棵生成树(奇环只有一条非树边)，任取一个叶子将点权和颜色同时归位，由于奇环上的两条路径奇偶性不同，可以保证取得需要的奇偶性。
最后只剩下环上的节点，用上述构造方法即可。

总结：从必要条件开始猜测结论

#include <queue>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int MAXN = 1e6;
int T , n , m , a[ MAXN + 5 ] , b[ MAXN + 5 ]; 
char c[ MAXN + 5 ] , d[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];

bool vis[ MAXN + 5 ]; int col[ MAXN + 5 ];
vector< int > S[ 2 ] , V;
bool Check( int s ) {
	bool f = 1;
	queue< int > q; S[ 0 ].clear(); S[ 1 ].clear();
	q.push( s ); S[ col[ s ] = 0 ].push_back( s );
	while( !q.empty() ) {
		int u = q.front(); q.pop();
		vis[ u ] = 1;
		for( int v : Graph[ u ] ) {
			if( col[ v ] == -1 ) {
				q.push( v );
				S[ col[ v ] = col[ u ] ^ 1 ].push_back( v ); 
			}
			else if( col[ v ] == col[ u ] ) f = 0;
		}
	}
	V.clear();
	for( int v : S[ 0 ] ) V.push_back( v ); for( int v : S[ 1 ] ) V.push_back( v ); 
	return f;
}

int main( ) {
//	freopen("graph.in","r",stdin);
//	freopen("graph.out","w",stdout);
	
	scanf("%d",&T);
	while( T -- ) {
		scanf("%d %d",&n,&m);
		for( int i = 1 , u , v ; i <= m ; i ++ ) {
			scanf("%d %d",&u,&v);
			Graph[ u ].push_back( v );
			Graph[ v ].push_back( u );
		} 
		for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
		scanf("%s", c + 1 );
		for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&b[ i ]);
		scanf("%s", d + 1 );
		
		bool f = 1;
		for( int i = 1 ; i <= n ; i ++ ) col[ i ] = -1;
		for( int i = 1 ; i <= n ; i ++ ) if( !vis[ i ] ) {
			if( Check( i ) ) { //二分图 
				unordered_map< int , int > cnt1 , cnt2;
				for( int u : V ) {
					if( col[ u ] == 0 ) {
						if( c[ u ] == 'B' ) cnt1[ a[ u ] ] ++;
						if( d[ u ] == 'B' ) cnt2[ b[ u ] ] ++;
					}
					if( col[ u ] == 1 ) {
						if( c[ u ] == 'R' ) cnt1[ a[ u ] ] ++;
						if( d[ u ] == 'R' ) cnt2[ b[ u ] ] ++;
					}
				}
				f &= cnt1 == cnt2;
				
				cnt1.clear(); cnt2.clear();
				for( int u : V ) {
					if( col[ u ] == 1 ) {
						if( c[ u ] == 'B' ) cnt1[ a[ u ] ] ++;
						if( d[ u ] == 'B' ) cnt2[ b[ u ] ] ++;
					}
					if( col[ u ] == 0 ) {
						if( c[ u ] == 'R' ) cnt1[ a[ u ] ] ++;
						if( d[ u ] == 'R' ) cnt2[ b[ u ] ] ++;
					}
				}
				f &= cnt1 == cnt2;
			}
			else {
				int cnta = 0 , cntb = 0;
				vector< int > va , vb;
				for( int u : V ) {
					cnta += c[ u ] == 'R'; cntb += d[ u ] == 'R';
					va.push_back( a[ u ] ); vb.push_back( b[ u ] );
				}
				sort( va.begin() , va.end() ); sort( vb.begin() , vb.end() );
				f &= ( cnta % 2 == cntb % 2 );
				for( int i = 0 ; i < va.size() ; i ++ ) f &= va[ i ] == vb[ i ]; 
			} 
		} 
		puts( f ? "YES" : "NO" );
		
		for( int i = 1 ; i <= n ; i ++ ) Graph[ i ].clear() , vis[ i ] = 0;
	}
	return 0;
}