AGC 052 B - Tree Edges XOR

• 考虑给点 \(u\) 定义权值 \(f_u\) 来描述对于边的操作。

  对于边 \((u,v,w)\) 需要 \(f_u\oplus f_v = w\)。

  那么每次操作相当于交换点值，但这样边集对应的点集不唯一。

  因为有奇数个点，可以强制令 \(\bigoplus_{u = 1}^n f_u = 0\)，这样是唯一确定的。

• 对根节点任意赋值，然后依次给儿子赋值即可得到一组点权的可重集 \(S\)。

  两种边集可通过操作变成对方，则经过操作后 \(S\) 相等。

  于是只需判断 \(S\) 是否相等，通过排序即可实现。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, h[N], cnt = 1, a[N], b[N], c;

struct Edge {
	int to, next, w1, w2;
} e[N<<1];

void add_(int u, int v, int w1, int w2) {
	e[++cnt] = (Edge) {v, h[u], w1, w2};
	h[u] = cnt;
}

void dfs_(int u, int fa) {
	c ^= a[u]^b[u];
	
	for (int v, i = h[u]; i; i = e[i].next) {
		v = e[i].to;
		
		if (v == fa)
			continue;
		
		a[v] = a[u]^e[i].w1, b[v] = b[u]^e[i].w2;
		dfs_(v, u);
	}
}

int main() {
	scanf("%d", &n);
	
	for (int u, v, w1, w2, i = 1; i < n; i++) {
		scanf("%d%d%d%d", &u, &v, &w1, &w2);
		add_(u, v, w1, w2);
		add_(v, u, w1, w2);
	}
	
	dfs_(1, 0);
	
	for (int i = 1; i <= n; i++)
		a[i] ^= c;

	sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
	
	for (int i = 1; i <= n; i++)
		if (a[i] != b[i])
			return puts("NO"), 0;
	
	puts("YES");
}

AGC 052 B - Tree Edges XOR

原文：https://www.cnblogs.com/iqx37f/p/14864361.html