[bzoj4568]-[SCOI2016]幸运数字

题目（BZOJ）
题目（洛谷）
 
直接倍增（打st表）维护线性基......
所以n才会给这么小啊......

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=20050;
int n,Q;
ll ji[N][16][70],mx[70];
int dep[N],p[N][16];
struct edge{
	int vk,nxt;
}e[N<<1];
int head[N],tt;
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
inline void addji(ll *x,ll v){
	for(int i=60;i>=0;--i){
		if(!(v>>i))continue;
		if(!x[i]){x[i]=v;break;}
		v^=x[i];
	}
}
inline void mergeji(ll *x,ll *y){
	for(int i=60;i>=0;--i){
		if(!y[i])continue;
		addji(x,y[i]);
	}
}
void dfslca(int u){
	for(int i=1;i<=15;++i){
		for(int j=0;j<=60;++j)ji[u][i][j]=ji[u][i-1][j];
		mergeji(ji[u][i],ji[p[u][i-1]][i-1]);
		p[u][i]=p[p[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].vk;
		if(v==p[u][0])continue;
		dep[v]=dep[u]+1;
		p[v][0]=u;
		dfslca(v);
	}
}
inline void lca(int x,int y){
	if(dep[y]<dep[x])swap(x,y);
	for(int i=15;i>=0;--i){
		if(dep[y]-(1<<i)<dep[x])continue;
		mergeji(mx,ji[y][i]);
		y=p[y][i];
	}
	if(x==y){
		mergeji(mx,ji[y][0]);
		return;
	}
	for(int i=15;i>=0;--i){
		if(p[x][i]==p[y][i])continue;
		mergeji(mx,ji[x][i]);mergeji(mx,ji[y][i]);
		x=p[x][i],y=p[y][i];
	}
	mergeji(mx,ji[x][0]);mergeji(mx,ji[y][0]);
	mergeji(mx,ji[p[y][0]][0]);
}
int main(){
	read(n),read(Q);
	for(int i=1;i<=n;++i){
		ll x;read(x);
		addji(ji[i][0],x);
	}
	for(int i=1;i<n;++i){
		int u,v;read(u),read(v);
		ad(u,v),ad(v,u);
	}
	dfslca(1);
	while(Q--){
		memset(mx,0,sizeof mx);
		int x,y;read(x),read(y);
		lca(x,y);ll ans=0;
		for(int i=60;i>=0;--i)ans=max(ans,(ans^mx[i]));
		printf("%lld\n",ans);
	}
	return 0;
}