C++14(g++5.4) 解法, 执行用时: 211ms, 内存消耗: 51220K, 提交时间: 2020-10-08 23:03:26

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

#define rep(i, a, n) for(int i=(a); i<(n); ++i)
#define per(i, a, n) for(int i=(a); i>(n); --i)
#define pb emplace_back
#define mp make_pair
#define clr(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x & -x)
#define fi first
#define se second
#define lson o<<1
#define rson o<<1|1
#define gmid l[o]+r[o]>>1
 
using LL = long long;
using ULL = unsigned long long;
using pii = pair<int,int>;
using PLL = pair<LL, LL>;
using UI = unsigned int;
 
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1.0);

const int N = 1e5 + 10;
const int M = 31;
const int L = 30;

int n;
int dfs_cnt, lft[N], rgt[N];
vector<int> V[N];
UI ans, dp[N][M], a[N], F[N][M], G[N][M], buf[M];

void join(UI *a, UI *b){
	UI x;
	per(i, L, -1){
		if(b[i] == 0)	continue;
		x = b[i];
		per(j, i, -1){
			if(!(x >> j))	continue;
			if(a[j] == 0){
				a[j] = x;
				break;
			}
			x ^= a[j];
		}
	}
}

void dfs(int x, int fa){
	lft[x] = ++dfs_cnt;

	rep(i, 0, M)	dp[x][i] = 0;
	per(i, L, -1){
		if(a[x] >> i & 1){
			dp[x][i] = a[x];
			F[dfs_cnt][i] = a[x];
			G[dfs_cnt][i] = a[x];
			break;
		}
	}

	for(int j : V[x]){
		if(j == fa)	continue;
		dfs(j, x);
		join(dp[x], dp[j]);
	}

	rgt[x] = dfs_cnt;
}

UI getval(UI *arr){
	UI ret = 0;
	per(i, L, -1){
		if((ret ^ arr[i]) > ret){
			ret ^= arr[i];
		}
	}
	return ret;
}

int main(){
	int x, y;
	scanf("%d", &n);
	rep(i, 1, n+1)	scanf("%u", a+i);
	rep(i, 1, n){
		scanf("%d %d", &x, &y);
		V[x].pb(y);
		V[y].pb(x);
	}
	dfs_cnt = 0;
	memset(F, 0, sizeof(F));
	memset(G, 0, sizeof(G));
	dfs(1, -1);
	ans = 0;
	rep(i, 1, n+1){
		join(F[i], F[i-1]);
	}
	per(i, n, 0){
		join(G[i], G[i+1]);
	}
	rep(i, 1, n+1){
		rep(j, 0, M)	buf[j] = 0;
		join(buf, F[lft[i] - 1]);
		join(buf, G[rgt[i] + 1]);
		ans = max(ans, getval(dp[i]) + getval(buf));
	}
	printf("%u\n", ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 240ms, 内存消耗: 42344K, 提交时间: 2018-04-15 12:47:55

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int l[MAXN],r[MAXN],ans,N,n,m,i,j,k,h[MAXN],ne[MAXN<<1],p[MAXN<<1],a[MAXN],d[MAXN];
struct node
{
	int a[30];
	void ins(int x)
	{
		int i;
		for(i=29;~i;i--)if(x>>i&1)
      {
			if(!a[i])a[i]=x;
			x^=a[i];
			if(!x)return;
		}
	}
	int ask()
	{
		int i,j=0;
		for(i=29;~i;i--)if((j^a[i])>j)j^=a[i];
		return j;
	}
	void operator+=(const node& y)
	{
		for(int i=0;i<30;i++)ins(y.a[i]);
	}
}w1[MAXN],w2[MAXN],w[MAXN],t;
void dfs(int x)
{
	d[l[x]=++N]=x;
	w[x].ins(a[x]);
	for(int i=h[x];i;i=ne[i])if(!l[p[i]])
	{
		dfs(p[i]);
		w[x]+=w[p[i]];
	}
	r[x]=N;
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&j,&k);
		p[++m]=k;
		ne[m]=h[j];
		h[j]=m;
		p[++m]=j;
		ne[m]=h[k];
		h[k]=m;
	}
	dfs(1);
	for(i=1;i<=n;i++)
	{
		w1[i]=w1[i-1];
		w1[i].ins(a[d[i]]);
	}
	for(i=n;i;i--)
	{
		w2[i]=w2[i+1];
		w2[i].ins(a[d[i]]);
	}
	for(i=2;i<=n;i++)
	{
		t=w1[l[i]-1];
		t+=w2[r[i]+1];
		ans=max(ans,w[i].ask()+t.ask());
	}
	cout<<ans<<endl;
	return 0;
}