AGC 052 B

题目

\(n\) 个点的数，\(n\) 为奇数，每条边有边权 \(a_i\)，有目标边权 \(b_i\)

每次操作选择一条边 \((u,v)\) 并且将所有与 \((u,v)\) 相连的边除 \((u,v)\) 之外全部异或上 \((u,v)\) 的边权

问能否经过若干次操作将每条边都变成目标边权

\(n \leq 10^5,a_i,b_i\le 2^{30}\)

题解

首先考虑边权转点权，第 \(i\) 个点赋值为 \(d_i\) ，使得每条边 \((u,v)=d_u\oplus d_v\) ，那么直接使 \(1\) 为根，\(d_u=\) 到 \(1\) 路径的异或和就是一种合法的赋值。

现在我们发现每个操作相当于交换了相邻两个点 \(u,v\) 的点权，那么最后点权的集合应该是不变的，所以只要点权集合相同，那么就一定有方案。

但是可以发现每个点的点权并非只有目前的一种解，事实上，对于每个 \(d_u\) 同时异或 \(x\)，就可以生成每一种解。

那么考虑类似的，推出 \(f_u\) 表示在目标树上每个点的点权，现在就想知道是否有一种解，在有解的情况下，两个集合应该满足\(f_1\oplus...f_n=(d_1\oplus x)\oplus...(d_n\oplus x)\)

因为总点数是奇数，那么可以发现最后右边只会剩下一个 \(x\)，那么我们就可以将这个 \(x\) 确定出来。

由于我们是在假设状态合法情况下推出的 \(x\)， 那么就反推出来 \(d\) 数组的取值，与 \(f\) 数组比较一下是否真的全部相同

const int N=2e5+5;
int n,x,y,xx,yy;
struct node{
	int next,to,d1,d2;
}a[N*2];
int head[N],cnt;
void add(int e,int r,int t,int tt){
	a[++cnt].next=head[e];
	a[cnt].to=r;a[cnt].d1=t;a[cnt].d2=tt;
	head[e]=cnt;
}
int c[N],d[N];
void dfs(int u,int fa){
	for(int i=head[u];i;i=a[i].next){
		if(a[i].to==fa)continue;
		c[a[i].to]=c[u]^a[i].d1;
		d[a[i].to]=d[u]^a[i].d2;
		dfs(a[i].to,u);
	}
}
int main(){
	#ifdef newbiewzs
	#else
	#endif
	n=read();
	for(int i=1;i=0;i--){
		if(!(xx&(1<<(i-1))) && (yy&(1<<(i-1))))tmp|=(1<<(i-1));
		if((xx&(1<<(i-1))) && !(yy&(1<<(i-1))))tmp|=(1<<(i-1));
	}
	for(int i=1;i<=n;i++){
		c[i]^=tmp;
	}
	sort(c+1,c+n+1);
	sort(d+1,d+n+1);
	for(int i=1;i<=n;i++){
		if(c[i]!=d[i]){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}