異或路徑

有一棵n個結點的樹，每個點都有一個點權，定義一條異或路徑的權值為該路徑上所有點權的異或值，問該棵樹的最大異或路徑權值。

輸入格式：

第一行1個整數n，表示樹的結點數。

接下來1行n個數ai表示每個結點點權。

接下來n-1行每行2個整數x、y，結點x和y之間有連邊。

輸出格式：

輸出一個整數ans表示最大異或路徑權值。

樣例輸入：

3

1 3 4

1 2

2 3

樣例輸出：

7

資料範圍：

20%的資料n<=10。

40%的資料n<=1000。

另有10%的資料0<=ai<=1。

100%的資料n<=30000，0<=ai<=2147483647。

時間限制：

1s

空間限制：

256M

提示：

路徑2-3的權值為3^4=7最大。

第次寫點分治啊。還是挺簡單的。

以這一道題為例，yy一下點分治的過程。

一、先找樹的重心。

有兩種方法找重心：

1.按定義找，當重心為根時，重心兒子的子樹Size最大的最小。

2.随便選一個點u，bfs一次找到離他最遠的點v,再以點v開始bfs找離他最遠的點w,則v--w的路徑一定是樹的直徑，直徑一半的位置的點就是重心。（記錄每個點的pre找，長度為偶數随便搞一個）

第一個找出來的當然是标準的重心，第二個不一定是标準的重心，但差最多也隻有1。

第一個應該要快一些。（雖然我很沙茶的寫的第二個）

二、以重心為根，統計經過重心的路徑。

這道題是統計xor最大路徑，用點權轉二進制建立trie。

由于是統計經過重心的路徑，路徑一定是上去，經過重心，再下來。

然後按順序找重心的兒子子樹，每一個節點記錄重心到該點的xor和，再在trie裡面query，更新答案。

計算完答案之後，就将每個節點的xor和加入到trie裡。

這樣是可以不漏的統計每條路徑的。

三、遞歸統計重心兒子子樹裡的路徑。

找每個兒子子樹的重心，然後和上面一樣搞。

因為每次找重心，是以深度期望是logN的，每層子樹要O(NlogN）處理，總複雜度是O(Nlog^2N)的

如果其他地方都沒錯，但是要TLE，那就着重要看重心找對沒有。

寫完之後我很意外啊，隻有90+行，實在是不長，之前以為要寫很多。

有幾個小技巧，因為分治的時候有很多邊不能走了，建立個數組儲存邊能不能走。

反向邊和網絡流一樣建，這樣k^1就是反向邊編号了。

trie樹是每次都需要清空的，memset肯定不行。

是以每次清空直接斷掉根節點的左右兒子，總Size=0,根節點num=0。

然後每次在記憶體池裡拿新節點的時候先把新節點初始化一下，就可以了。

#include <cstdio>
#include <algorithm>
#define rep(i,l,r) for (int i=l;i<=r;++i)
#define per(i,r,l) for (int i=r;i>=l;--i)
bool upmax(int &a,const int &b){return a<b?a=b,1:0;}
const int MAX_N=30050;
int getx(){
	char c;int x;
	for (c=getchar();c<'0'||c>'9';c=getchar());
	for (x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x;
}
int n;
int first[MAX_N],next[MAX_N<<2],to[MAX_N<<2];
bool can[MAX_N<<2];
int w[MAX_N],tal=1;
void tjb(int x,int y){
	next[++tal]=first[x];
	first[x]=tal;
	to[tal]=y;
	can[tal]=true;
}
int ch[MAX_N*32][2],num[MAX_N*32],tot=1;
void insert(int v,int x,int p){
	num[v]++;
	if (p<0) return;
	int i=(x>>p)&1;
	if (!ch[v][i]) ch[v][i]=++tot,ch[tot][0]=ch[tot][1]=0,num[tot]=0;
	insert(ch[v][i],x,p-1);
}
int query(int v,int x,int p){
	if (!num[v]||p<0) return 0;
	int i=(x>>p)&1;
	if (num[ch[v][!i]]) return (1<<p)+query(ch[v][!i],x,p-1);
	else return query(ch[v][i],x,p-1);
}
int que[MAX_N],pre[MAX_N];
int bfs(int S){
	int t=0,h=0,u,v;
	que[t]=S;pre[S]=0;
	while (t<=h){
		u=que[t++];
		for (int k=first[u];k;k=next[k]){
			if (can[k]&&(v=to[k])!=pre[u]){
				pre[v]=u;que[++h]=v;
				}
			}
		}
	return que[h];
}
int findg(int x){
	int v=bfs(bfs(x)),p=v;
	int len=0;
	do len++;while((p=pre[p])!=0);
	len/=2;
	while (len-->0) v=pre[v];
	return v;
}
int ans=0;
int xors[MAX_N];
void work(int v,int lcaw){
	int t=0,h=0,u;
	que[t]=v;xors[v]=w[v];pre[v]=0;
	while (t<=h){
		u=que[t++];
		upmax(ans,query(1,xors[u],31));
		for (int k=first[u];k;k=next[k]){
			if (can[k]&&(v=to[k])!=pre[u]){
				xors[v]=xors[u]^w[v];
				pre[v]=u,que[++h]=v;
				}
			}
		}
	rep(i,0,h) insert(1,xors[que[i]]^lcaw,31);
}
void dfs(int v){
	int g=findg(v);
	tot=1;ch[1][0]=ch[1][1]=0;
	insert(1,0,31);insert(1,w[g],31);
	for (int k=first[g];k;k=next[k])
		if (can[k]) {can[k^1]=false;work(to[k],w[g]);can[k^1]=true;}
	for (int k=first[g];k;k=next[k])
		if (can[k]) {can[k^1]=false;dfs(to[k]);can[k^1]=true;}
}
int main(){
	n=getx();
	rep(i,1,n) w[i]=getx();
	rep(i,2,n){
		int x=getx(),y=getx();
		tjb(x,y),tjb(y,x);
		}
	dfs(1);
	printf("%d\n",ans);
}