AGC052 B - Tree Edges XOR Editorial

题目：B - Tree Edges XOR

题目描述：
给你一棵\(n\)个点、\(n-1\)条边的树，树上每条边的边权\(w_{i}^{1}\)和期望边权\(w_{i}^{2}\)均已知（\(w_{i}^{2}\)不是\(w_{i}^{1}\)平方的意思），你可以进行以下操作

• 选择一条边\((a,b)\)，记这条边现在的权值为\(w\)，那么与这条边相邻的所有边，即所有的\((a,x)\)和\((b,y)\)（边\((a,b)\)不算）的边权值都会异或上\(w\)

你可以进行任意次数操作，问是否存在合法的操作使得所有的边权\(w_{i}^{1}\)都变为它对应的期望边权\(w_{i}^{2}\)

\(n \leq 10^{5}\) 且 \(n\) 为奇数， \(0 \leq w_{i}^{1},w_{i}^{2} < 2^{30}\)

蒟蒻题解
我真的是太菜了，一场比赛就打了一个第一题，第二题就不会了

定义\(d_{u,v}\)表示\(u\)到\(v\)的简单路径上所有边的权值的异或和（这个想法是我之前没怎么接触到的），\(f_{u,v}\)表示\(u\)到\(v\)的简单路径上所有边的期望权值的异或和

当对边\((a,b)\)进行操作时

• 若\(u \neq a\)且\(u \neq b\)，则\(d_{u,a}\)的值和\(d_{u,b}\)的值会进行交换
• 若\(u = a\)或\(u = b\)，假设\(u = a\)，记\((u,b)\)这条边的权值为\(w\)，则对于任意点\(v\)，\(d_{u,v}\)都会异或上\(w\)

假设对以点\(u\)为端点的所有边的操作异或起来记为\(W\)，那么如果答案有解，那么对于任意点\(a\)，一定存在\(d_{u,a} \bigoplus W = f_{u,b}\)，且\(a\)和\(b\)两两配对

如果存在满足条件的\(W\)，由于\(n\)是奇数，所有易得\(W = d_{u,1} \bigoplus d_{u,2} \bigoplus ··· \bigoplus d_{u,n} \bigoplus f_{u,1} \bigoplus f_{u,2} \bigoplus ··· \bigoplus f_{u,n}\)

那么题目可以转换为：是否存在合法操作，使得对于任意点\(u\)，以\(u\)为端点的边的操作异或能构成\(W\)，且\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)两两对应相等

假设对于一个点\(u\)，想要判断是否存在操作能来构成\(W\)不太好做，我们可以先看看后面的要求：要满足\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)两两对应相等

由于我们已知\(W = d_{u,1} \bigoplus d_{u,2} \bigoplus ··· \bigoplus d_{u,n} \bigoplus f_{u,1} \bigoplus f_{u,2} \bigoplus ··· \bigoplus f_{u,n}\)，那么\(d_{u,a} \bigoplus W = f_{u,b}\)就相当于\(d_{u,a} \bigoplus W \bigoplus f_{u,b} = 0\)，即将构成\(W\)的一系列异或值去掉\(d_{u,a}\)和\(f_{u,b}\)，其他值异或起来为\(0\)，也就是说\(d_{u,1} \bigoplus d_{u,2} \bigoplus ··· \bigoplus d_{u,a-1} \bigoplus d_{u,a+1} \bigoplus ··· \bigoplus d_{u,n} = f_{u,1} \bigoplus f_{u,2} \bigoplus ··· \bigoplus f_{u,b-1} \bigoplus f_{u,b+1} \bigoplus ··· \bigoplus f_{u,n}\)，也就是说，我们能用若干\(d_{u,x}\)去表示\(f_{u,y}\)，原本构成\(W\)需要\(d\)和\(f\)，可以全部转换成\(d\)的形式，所以如果满足\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)两两对应相等，那么\(W\)也能被构建出来

但是一共有\(n\)个点，每个点都去判断一次，单次判断复杂度是\(O(nlog\ n)\)，总的复杂度是\(O(n^{2}log\ n)\)的

不妨去试一下，一个点成立，能否推广到其他点也成立

若\(u\)满足条件，那么假设\(v\)与\(u\)有连边，这条边的初始权值为\(w ^ {1}\)，期望权值为\(w ^{2}\)，那么\(d_{v,a} = d_{u,a} \bigoplus w ^ {1}\)，\(f_{v,a} = f_{u,a} \bigoplus w ^ {2}\)，\(W_{v} = W_{u} \bigoplus w ^ {1} \bigoplus w ^ {2}\)，假设原本存在\(d_{u,a} \bigoplus W_{u} = f_{u,b}\)，那么现在\(d_{v,a} \bigoplus W_{v} = f_{v,b}\)也同样成立

总结：对于节点\(u\)，判断是否存在\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)两两对应相等，时间复杂度是\(O(nlog\ n)\)

参考程序：

#include<bits/stdc++.h>
using namespace std;
#define Re register int

const int N = 100005;
int n, cnt, s, val1[N], val2[N], hea[N], nxt[N << 1], to[N << 1], wi1[N << 1], wi2[N << 1];

inline int read()
{
	char c = getchar();
	int ans = 0;
	while (c < 48 || c > 57) c = getchar();
	while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
	return ans;
}

inline void add(int x, int y, int z1, int z2)
{
	nxt[++cnt] = hea[x], to[cnt] = y, wi1[cnt] = z1, wi2[cnt] = z2, hea[x] = cnt;
}

inline void dfs(int x, int y)
{
	for (Re i = hea[x]; i; i = nxt[i])
	{
		int u = to[i];
		if (u == y) continue;
		val1[u] = val1[x] ^ wi1[i], val2[u] = val2[x] ^ wi2[i];
		dfs(u, x);
	}
}

int main()
{
	n = read();
	for (Re i = 1; i < n; ++i)
	{
		int u = read(), v = read(), w1 = read(), w2 = read();
		add(u, v, w1, w2), add(v, u, w1, w2);
	}
	dfs(1, 0);
	for (Re i = 1; i <= n; ++i) s ^= val1[i] ^ val2[i];
	for (Re i = 1; i <= n; ++i) val1[i] ^= s;
	sort(val1 + 1, val1 + n + 1), sort(val2 + 1, val2 + n + 1);
	for (Re i = 1; i <= n; ++i)
		if (val1[i] ^ val2[i])
		{
			puts("NO");
			return 0;
		}
	puts("YES");
	return 0;
}