出题人题解 | #Xor Path#

原题解链接：https://ac.nowcoder.com/discuss/150246

对每个点，考虑它被多少条路径经过。在枚举子树的时候用$sizesize$算一下就可以了。

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e6+5;

int n,Ans,Enum,H[N],nxt[N<<1],to[N<<1],A[N],sz[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS(int x,int fa)
{
	sz[x]=1;
	for(int i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa) DFS(v,x), sz[x]+=sz[v];
	LL tmp=n-sz[x];
	for(int s=n-sz[x]+1,i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa) tmp+=1ll*s*sz[v], s+=sz[v];
	if(tmp&1) Ans^=A[x];
}/*
4
1 2
1 3
1 4
1 2 3 4

3
1 2
1 3
1 2 3
*/

int main()
{
//	freopen("xor.in","r",stdin);
//	freopen("xor.out","w",stdout);
	
	n=read();
	for(int i=1; i<n; ++i) AE(read(),read());
	for(int i=1; i<=n; ++i) A[i]=read();
	DFS(1,1), printf("%d\n",Ans);

	fclose(stdin), fclose(stdout);
	return 0;
}