自动搬运

查看原文

来自洛谷，原作者为

	夜猫子驱蚊器 败犬

搬运于2025-08-24 21:47:24，当前版本为作者最后更新于2019-08-08 18:25:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的博客，欢迎来踩( • ̀ω•́ )✧

提供一个两个log的在线做法，有点类似kcz说的序列做法
kcz说的那个，可以去做这题，裸的

对每一个点，我们可以预处理出从根到它的线性基，并且贪心的让高位的向量对应的点深度尽量大，并预处理出 $pos[x][i]$ 表示 $x$ 号结点第 $i$ 位的向量对应最深的点，可以用以下代码求出。

LL bas[N][61];
int pos[N][61];
void ins(int p,LL bas[],int pos[]){
	LL x=a[p];
	if (x==0) return;
	rf(i,60,0)
	 if ((x>>i)&1){
	 	if (!bas[i]){
	 		bas[i]=x;pos[i]=p;
	 		break;
		}
		if (dep[p]>dep[pos[i]]) swap(pos[i],p),swap(x,bas[i]); //确保第i位深度尽量大
		x^=bas[i];
	 }
}

这样写正确性是显然的，当第 $i$ 位碰到了一个更深的点的时候，就相当于交换了一下插入的顺序。

然后对于一个查询 $x,y$ ，假设其LCA深度为 $d$ ，我们只取 $pos[x][i] \geq d$ 和 $pos[y][i] \geq d$ 的那些向量，暴力合并就行了ヾ(◍°∇°◍)ﾉﾞ

这个算法跑得很快，我也没特意卡常，就洛谷第二页（开O2就rank2）了，BZOJ是rank5。
作为kcz的小迷妹，在此悄悄%%%kcz

最后贴一下丑陋的代码，感觉比点分什么的好写啊~

#include<bits/stdc++.h>
#define LL long long
#define re register
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
#define frz(i,x,y) for(int i=x,z=y;i<=z;i++)
using namespace std;
const int N=20002;
const int M=N<<1;
const int Lg=15;
int n,q;
LL a[N];
int cnt,head[N],Next[M],v[M];

inline void read(int &x){
	char ch=getchar();x=0;int w=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	if (w) x=-x;
}
inline void read(LL &x){
	char ch=getchar();x=0;int w=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	if (w) x=-x;
}

void add(int x,int y){ Next[++cnt]=head[x];head[x]=cnt;v[cnt]=y; }

int dep[N],f[N][Lg];
LL bas[N][61];
int pos[N][61];
void ins(int p,LL bas[],int pos[]){
	LL x=a[p];
	if (x==0) return;
	rf(i,60,0)
	 if ((x>>i)&1){
	 	if (!bas[i]){
	 		bas[i]=x;pos[i]=p;
	 		break;
		}
		if (dep[p]>dep[pos[i]]) swap(pos[i],p),swap(x,bas[i]);
		x^=bas[i];
	 }
}

void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	frl(i,1,Lg) f[x][i]=f[f[x][i-1]][i-1];
	
	fr(i,0,60) pos[x][i]=pos[fa][i],bas[x][i]=bas[fa][i];
	ins(x,bas[x],pos[x]);
	
	for(int i=head[x];i;i=Next[i])
	 if (v[i]!=fa) dfs(v[i],x);
}

int getLCA(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	rf(i,Lg-1,0) if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	rf(i,Lg-1,0) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

LL base[61];
int main(){
	read(n);read(q);
	fr(i,1,n) read(a[i]);
	int x,y;
	fr(i,2,n){
		read(x);read(y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	while(q--){
		read(x);read(y);
		int lca=getLCA(x,y);
		rf(i,60,0) if (dep[pos[x][i]]>=dep[lca]) base[i]=bas[x][i];else base[i]=0;
		rf(i,60,0)
		 if (dep[pos[y][i]]>=dep[lca]){
		 	LL x=bas[y][i];
		 	if (x==0) continue;
		 	rf(j,i,0)
		 	 if ((x>>j)&1){
		 	 	if (!base[j]){ base[j]=x;break; }
				x^=base[j];
			 }
		 }
		LL ans=0;
		rf(i,60,0) if ((ans^base[i])>ans) ans^=base[i];
		printf("%lld\n",ans);
	}
	return 0;
}