題目：B - Tree Edges XOR

題目描述：
給你一棵\(n\)個(gè)點(diǎn)、\(n-1\)條邊的樹(shù)，樹(shù)上每條邊的邊權(quán)\(w_{i}^{1}\)和期望邊權(quán)\(w_{i}^{2}\)均已知（\(w_{i}^{2}\)不是\(w_{i}^{1}\)平方的意思），你可以進(jìn)行以下操作

• 選擇一條邊\((a,b)\)，記這條邊現(xiàn)在的權(quán)值為\(w\)，那么與這條邊相鄰的所有邊，即所有的\((a,x)\)和\((b,y)\)（邊\((a,b)\)不算）的邊權(quán)值都會(huì)異或上\(w\)

你可以進(jìn)行任意次數(shù)操作，問(wèn)是否存在合法的操作使得所有的邊權(quán)\(w_{i}^{1}\)都變?yōu)樗鼘?duì)應(yīng)的期望邊權(quán)\(w_{i}^{2}\)

\(n \leq 10^{5}\) 且 \(n\) 為奇數(shù)， \(0 \leq w_{i}^{1},w_{i}^{2} < 2^{30}\)

蒟蒻題解
我真的是太菜了，一場(chǎng)比賽就打了一個(gè)第一題，第二題就不會(huì)了

定義\(d_{u,v}\)表示\(u\)到\(v\)的簡(jiǎn)單路徑上所有邊的權(quán)值的異或和（這個(gè)想法是我之前沒(méi)怎么接觸到的），\(f_{u,v}\)表示\(u\)到\(v\)的簡(jiǎn)單路徑上所有邊的期望權(quán)值的異或和

當(dāng)對(duì)邊\((a,b)\)進(jìn)行操作時(shí)

• 若\(u \neq a\)且\(u \neq b\)，則\(d_{u,a}\)的值和\(d_{u,b}\)的值會(huì)進(jìn)行交換
• 若\(u = a\)或\(u = b\)，假設(shè)\(u = a\)，記\((u,b)\)這條邊的權(quán)值為\(w\)，則對(duì)于任意點(diǎn)\(v\)，\(d_{u,v}\)都會(huì)異或上\(w\)

假設(shè)對(duì)以點(diǎn)\(u\)為端點(diǎn)的所有邊的操作異或起來(lái)記為\(W\)，那么如果答案有解，那么對(duì)于任意點(diǎn)\(a\)，一定存在\(d_{u,a} \bigoplus W = f_{u,b}\)，且\(a\)和\(b\)兩兩配對(duì)

如果存在滿足條件的\(W\)，由于\(n\)是奇數(shù)，所有易得\(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}\)

那么題目可以轉(zhuǎn)換為：是否存在合法操作，使得對(duì)于任意點(diǎn)\(u\)，以\(u\)為端點(diǎn)的邊的操作異或能構(gòu)成\(W\)，且\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)兩兩對(duì)應(yīng)相等

假設(shè)對(duì)于一個(gè)點(diǎn)\(u\)，想要判斷是否存在操作能來(lái)構(gòu)成\(W\)不太好做，我們可以先看看后面的要求：要滿足\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)兩兩對(duì)應(yīng)相等

由于我們已知\(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āng)于\(d_{u,a} \bigoplus W \bigoplus f_{u,b} = 0\)，即將構(gòu)成\(W\)的一系列異或值去掉\(d_{u,a}\)和\(f_{u,b}\)，其他值異或起來(lái)為\(0\)，也就是說(shuō)\(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}\)，也就是說(shuō)，我們能用若干\(d_{u,x}\)去表示\(f_{u,y}\)，原本構(gòu)成\(W\)需要\(d\)和\(f\)，可以全部轉(zhuǎn)換成\(d\)的形式，所以如果滿足\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)兩兩對(duì)應(yīng)相等，那么\(W\)也能被構(gòu)建出來(lái)

但是一共有\(n\)個(gè)點(diǎn)，每個(gè)點(diǎn)都去判斷一次，單次判斷復(fù)雜度是\(O(nlog\ n)\)，總的復(fù)雜度是\(O(n^{2}log\ n)\)的

不妨去試一下，一個(gè)點(diǎn)成立，能否推廣到其他點(diǎn)也成立

若\(u\)滿足條件，那么假設(shè)\(v\)與\(u\)有連邊，這條邊的初始權(quán)值為\(w ^ {1}\)，期望權(quán)值為\(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}\)，假設(shè)原本存在\(d_{u,a} \bigoplus W_{u} = f_{u,b}\)，那么現(xiàn)在\(d_{v,a} \bigoplus W_{v} = f_{v,b}\)也同樣成立

總結(jié)：對(duì)于節(jié)點(diǎn)\(u\)，判斷是否存在\(d_{u,a} \bigoplus W\)和\(f_{u,b}\)兩兩對(duì)應(yīng)相等，時(shí)間復(fù)雜度是\(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;
}