[文章目录]
Description
A 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 x 号城市，沿着 x 号城市到 y 号城市之间那条唯一的路径游览，最终从 y 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了 3 张照片，幸运值分别是 5，7，11，那么最终保留在自己身上的幸运值就是 9（5 xor 7 xor 11）。有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 5 和 11 ，可以保留的幸运值为 14 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。N<=20000,Q<=200000,Gi<=2^60
ST算法，倍增的同时维护线性基的合并即可。复杂度O(3600nlogn)
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 21000
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
inline ll read_ll()
{
ll re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
struct base
{
ll b[61];
base(){memset(b,0,sizeof b);}
void insert(ll x)
{
for(int i=60;~i;--i) if((x>>i)&1)
{
if(b[i]) x^=b[i];
else {b[i]=x; break;}
}
}
base operator + (const base &z) const
{
base re=*this;
for(int i=60;~i;--i) if(z.b[i]) re.insert(z.b[i]);
return re;
}
ll Max()
{
ll re=0;
for(int i=60;~i;--i)
re=max(re,re^b[i]);
return re;
}
}b[N][18];
int n,m,dep[N],fa[N][18],Log[N];
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
void dfs(int x,int pre)
{
for(int i=1;i<=Log[dep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,dfs(to[i],x);
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int tmp=dep[x]-dep[y];
for(int i=Log[tmp];~i;--i) if((tmp>>i)&1) x=fa[x][i];
if(x==y) return x;
for(int i=Log[dep[x]];~i;--i)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int find_fa(int x,int t)
{
for(int i=Log[t];~i;--i)
if((t>>i)&1) x=fa[x][i];
return x;
}
base find(int x,int t)
{
int lo=Log[t+1];
return b[x][lo]+b[find_fa(x,t+1-(1<<lo))][lo];
}
int main()
{
n=read(); m=read(); int i;
for(i=1;i<=n;++i)
b[i][0].insert(read_ll());
for(i=1;i<n;++i) add(read(),read());
for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
dfs(1,0); int j;
for(i=1;i<=Log[n];++i)
for(j=1;j<=n;++j)
b[j][i]=b[j][i-1]+b[fa[j][i-1]][i-1];
int anc;
while(m--)
{
i=read(); j=read();
anc=lca(i,j);
printf("%lld\n",(find(i,dep[i]-dep[anc])+find(j,dep[j]-dep[anc])).Max());
}
return 0;
}