C++14(g++5.4) 解法, 执行用时: 307ms, 内存消耗: 44220K, 提交时间: 2020-08-12 12:33:31

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 5e5+10;

int a[N],sz[N];
vector<int> g[N];
int n,ans;

void dfs(int u,int fa){
	sz[u]=1;
	int cnt=n-1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa) continue;
		dfs(v,u);
		cnt+=(n-sz[v])*sz[v];
		sz[u]+=sz[v];
	}
	cnt+=sz[u]*(n-sz[u]);
	cnt/=2;
	if(cnt%2) ans^=a[u];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u].pb(v);
		g[v].pb(u);
	}
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	dfs(1,0);
	printf("%d",ans);
	return 0;
}

C++(clang++11) 解法, 执行用时: 289ms, 内存消耗: 42104K, 提交时间: 2020-12-25 13:09:24

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define pb push_back
int a[N],sz[N],n;
vector<int>e[N];
int ans;
void dfs(int u,int fa){
    sz[u]=1;
    int s=0;
    for(int v:e[u]){
       if(v==fa) continue;
        dfs(v,u),sz[u]+=sz[v];
        if(sz[v]&1) s++;
    }
    int t=(n-1+1LL*(sz[u]-1)*(n-sz[u])%2+s*(s-1)/2%2)%2;
    ans^=(t*a[u]);
}
int main(){
    scanf("%d",&n);for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dfs(1,0);
    printf("%d\n",ans);
}