思路

首先观察，两个城市之间的路径一定是$x$->$lca$->$y$，这一条路上的数一定是固定的，我们只需要知道在这些数中选若干个使得他们的异或和最大。

一开始想到这里就没思路了，但是我打开题库一搜，就出来了这个区间异或和最大（线性基）（还没学过线性基的出门左转）。点开一看，是不是很眼熟？这其实就可以很方便的解决，只需要做一些变动。

首先，我们把这一条路先拆成两端：$x$->$lca$和$y$->$lca$因为这两段的深度都是连续的，我们的基的序列就可以按照每一个节点的深度来定义，找一个区间的异或和最大就转换为一段连续的深度的数的异或和最大。（为什么这么多“的”）

最终做法如下：

首先进行一遍$dfs$，同时预处理$LCA$和插入线性基（如代码中ins函数）。

其次，在询问的时候首先查找一下$x$和$y$的最近公共祖先（还不清楚的出门左转或出门右转或出门直走（这个解释最详细））

最后，将$x$->$lca$的基上的点存储下来，再将$y$->$lca$上的点存储下来（其实是把两个基合并，具体方法和插入一样），最后计算答案输出即可。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10;
vector<int>G[N];
int dep[N],fa[N][16];
int pos[N][61],p[N][61];
int a[N],b[61];
void ins(int x,int xfa)
{
	for(int i=0;i<=60;i++)p[x][i]=p[xfa][i],pos[x][i]=pos[xfa][i];
	int X=a[x],P=x;//当前基的数值和位置 
	for(int i=60;i>=0;i--)if(X>>i&1)
	{
		if(!p[x][i])
		{
			p[x][i]=X;pos[x][i]=P;
			break;
		}
		if(dep[pos[x][i]]<dep[P])swap(pos[x][i],P),swap(p[x][i],X);
		X^=p[x][i];
	}
}
void dfs(int x,int xfa)
{
	dep[x]=dep[xfa]+1;fa[x][0]=xfa;//预处理 
	for(int i=1;i<=15;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	ins(x,xfa);
	for(int i:G[x])if(i!=xfa)dfs(i,x);
}
int LCA(int x,int y)//这里用的是ST表，像重链，dfs序等方式因该也行 
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=15;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=15;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int query(int x,int y)
{
	int lca=LCA(x,y);
	for(int i=60;i>=0;i--)//先把x的基记录下来 
	{
		if(dep[pos[x][i]]>=dep[lca])b[i]=p[x][i];
		else b[i]=0;
	}
	for(int i=60;i>=0;i--)if(dep[pos[y][i]]>=dep[lca])//合并两个基（x,y） 
	{
		int X=p[y][i];
		for(int j=i;j>=0;j--)if(X>>j&1)
		{
			if(!b[j]){b[j]=X;break;}//没出现过就加入 
			X^=b[j];//有过就异或一下 
		}
	}
	int ans=0;
	for(int i=60;i>=0;i--)ans=max(ans,ans^b[i]);//记录结果 
	return ans;
}
signed main()
{
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1,x,y;i<n;i++)
	{
		scanf("%lld%lld",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);//进行预处理 
	while(m--)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		printf("%lld\n",query(x,y));//输出答案 
	}
	return 0;//完结撒花 
}

后记

比赛过程中我自己现学的线性基，最后也是把董晓的代码抄了一遍有调了20+分钟才AC的。

前提概要

先看 这道题 ;

线性基用于处理整个区间异或和的问题，前缀线性基用于处理一段区间异或和的问题。

讲解

前缀线性基 & 树上倍增 ： 先进行树上倍增，预处理 $dep$ (记录深度) 和 $fa$ (记录祖先) 。 对于任意节点，尽量使高位的线性基对应点的深度大，并预处理出 $p$ （ $p_{u,i}$ 表示节点 $u$ 第 $i$ 位的线性基 ） $pos$ ( $pos_{u,i}$ 表示节点 $u$ 第 $i$ 位线性基对应的最深点的编号) 。

区间查询 ：

先得到 $x$ 和 $y$ 的最近公共祖先 $z$ ，拆成 $x->z$ 和 $y->z$ 两条链，暴力合并两条链上的线性基。重构线性基后，易得最大值。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10;
vector<int>G[N];
int dep[N];
int fa[N][16];//ST表记录祖先 
int pos[N][61],p[N][61];
int a[N],b[61];
void ins(int x,int xfa)
{
	for(int i=0;i<=60;i++)p[x][i]=p[xfa][i],pos[x][i]=pos[xfa][i];
	int X=a[x],P=x;//当前基的数值和位置 
	for(int i=60;i>=0;i--)if(X>>i&1)//前缀线性基的ins函数 
	{
		if(!p[x][i]){//不存在就加入 
			p[x][i]=X;pos[x][i]=P;
			break;
		}
		//存在就先交换后异或 
		if(dep[pos[x][i]]<dep[P])swap(pos[x][i],P),swap(p[x][i],X);
		X^=p[x][i];
	}
}
void dfs(int x,int xfa){//预处理dep和p 
	dep[x]=dep[xfa]+1;fa[x][0]=xfa;
	for(int i=1;i<=15;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	ins(x,xfa);//构造线性基 
	for(int i:G[x])if(i!=xfa)dfs(i,x);
}
int LCA(int x,int y)//这里用的是ST表，像重链，dfs序等方式因该也行 
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=15;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=15;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int query(int x,int y)
{
	int lca=LCA(x,y);
	for(int i=60;i>=0;i--)//提取x->z的基
	{
		if(dep[pos[x][i]]>=dep[lca])b[i]=p[x][i];
		else b[i]=0;
	}
	for(int i=60;i>=0;i--)if(dep[pos[y][i]]>=dep[lca])//合并两个基（x,y） 
	{
		int X=p[y][i];
		for(int j=i;j>=0;j--)if(X>>j&1)//提取y->z的基 
		{
			if(!b[j]){b[j]=X;break;}//没出现过就加入 
			X^=b[j];//有过就异或一下 
		}
	}
	int ans=0;
	for(int i=60;i>=0;i--)ans=max(ans,ans^b[i]);
	return ans;
}
signed main()
{
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1,x,y;i<n;i++)
	{
		scanf("%lld%lld",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);//进行预处理 
	while(m--)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		printf("%lld\n",query(x,y));
	}
	return 0;
}

线性基+倍增，思路好想，代码好打，时间略慢

注意：1.要把st[][]初始化 2.要注意运算优先级，要加括号

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 20010
int n,q;
int a[N];
vector<int>G[N];
int dep[N],D;
struct node{
	int x,val[65];
	node(){
		for(int i=0;i<=60;i++)val[i]=0;
	}
	void add(int x){
		for(int i=60;i>=0;i--){
			if(!((1ll<<i)&x))continue;
			if(!val[i]){
				val[i]=x;
				break;
			}
			x^=val[i];
		}
	}
}st[N][20];
void dfs(int x,int xfa){
	dep[x]=dep[xfa]+1;
	st[x][0].x=xfa;for(int i=1;i<=D;i++)st[x][i].x=st[st[x][i-1].x][i-1].x;
	for(int y:G[x])if(y!=xfa){
		st[y][0].add(a[x]);
		st[y][0].add(a[y]);
		dfs(y,x);
	}
}
int solve(int x,int y){
	node ans;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=D;i>=0;i--)if(dep[st[x][i].x]>=dep[y]){
		for(int j=60;j>=0;j--){
			if(st[x][i].val[j])ans.add(st[x][i].val[j]);
		}
		x=st[x][i].x;
	}
	for(int i=D;i>=0;i--)if(st[x][i].x!=st[y][i].x){
		for(int j=60;j>=0;j--){
			if(st[x][i].val[j])ans.add(st[x][i].val[j]);
			if(st[y][i].val[j])ans.add(st[y][i].val[j]);
		}
		x=st[x][i].x,y=st[y][i].x;
	}
	if(x!=y){
		for(int i=60;i>=0;i--){
			if(st[x][0].val[i])ans.add(st[x][0].val[i]);
			if(st[y][0].val[i])ans.add(st[y][0].val[i]);
		}
	}
	int get=0;
	for(int i=60;i>=0;i--){
		if((get^ans.val[i])>get)get^=ans.val[i];
	}
	return get;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}a[0]=0;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		G[x].push_back(y);G[y].push_back(x);
	}
	
	D=log2(n);
	dfs(1,0);
	for(int j=1;j<=D;j++){
		for(int i=1;i<=n;i++){
			for(int k=0;k<=60;k++)st[i][j].val[k]=st[i][j-1].val[k];
			for(int k=0;k<=60;k++){
				if(st[st[i][j-1].x][j-1].val[k])st[i][j].add(st[st[i][j-1].x][j-1].val[k]);
			}
		}
	}
	
	while(q--){
		int x,y;cin>>x>>y;
		if(x==y)cout<<a[x]<<'\n';
		else cout<<solve(x,y)<<'\n';
	}
	
	return 0;
}

G70 前缀线性基+贪心法+LCA P3292 [SCOI2016] 幸运数字

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e4+10, M=N<<1;
vector<int>G[N];
int dep[N],f[N][20],D;
LL g[N],bas[N][61];
int pos[N][61];
void ins(int x,LL bass[],int poss[]) 
{
	LL v=g[x];if(v==0) return;
	for(int i=60; i>=0; i--)if((v>>i)&1) 
	{
		if(!bass[i]) {bass[i]=v;poss[i]=x;break;}
		if(dep[x]>dep[poss[i]])
		{
			swap(x,poss[i]),swap(v,bass[i]);
		}
		v^=bass[i];
	}
}

void dfs(int x,int fa) 
{
	dep[x]=dep[fa]+1;
	f[x][0]=fa;for(int i=1; i<=D; i++)f[x][i]=f[f[x][i-1]][i-1];

	memcpy(pos[x],pos[fa],sizeof(pos[x]));memcpy(bas[x],bas[fa],sizeof(bas[x]));
	ins(x,bas[x],pos[x]);

	for(int y:G[x])if(y!=fa)
	{
		dfs(y,x);
	}
}

int LCA(int x,int y) 
{
	if (dep[x]<dep[y]) swap(x,y);
	for(int i=D; i>=0; i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if (x==y) return x;
	for(int i=D; i>=0; i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}

int main() 
{
	int n,q;scanf("%d%d",&n,&q);
	for(int i=1; i<=n; i++)scanf("%lld",&g[i]);
	for(int i=1,x,y; i<n; i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);G[y].push_back(x);
	}
	dep[0]=0;D=log2(n);
	dfs(1,0);
	while(q--) 
	{
		int x,y;scanf("%d%d",&x,&y);
		int lca=LCA(x,y);
		LL bass[61];
		for(int i=60; i>=0; i--)if(dep[pos[x][i]]>=dep[lca]) bass[i]=bas[x][i];else bass[i]=0;
		for(int i=60; i>=0; i--)
			if (dep[pos[y][i]]>=dep[lca]) 
			{
				LL v=bas[y][i];if(v==0)continue;
				for(int j=i; j>=0; j--)if ((v>>j)&1)
					if (!bass[j]) {bass[j]=v;break;} 
					else v^=bass[j];
			}
		LL ans=0;
		for(int i=60; i>=0; i--)ans=max(ans,ans^bass[i]);
		printf("%lld\n",ans);
	}
	return 0;
}