题面

$A$ 国共有 $n$ 座城市，这些城市由 $n-1$ 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览 $A$ 国。旅行者计划乘飞机降落在 $x$ 号城市，沿着 $x$ 号城市到 $y$ 号城市之间那条唯一的路径游览，最终从$ y$ 城市起飞离开 $A$ 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了 $3$张照片，幸运值分别是 $5，7，11$，那么最终保留在自己身上的幸运值就是 $9（5 xor 7 xor 11）$。有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 $5$ 和 $11$ ，可以保留的幸运值为 $14$ 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

思路

简化一下题面，给你一棵树，树上点有点权，多次询问点对${u,v}$之间选任意一些点，点权异或最大值为多少。这题学过线性基的人应该都可以一眼秒掉吧（除了我），没学过线性基的人可以看看我的博客线性基小结(写的比较🧠level up，不喜请喷)。那么这题就是一个暴力倍增，并且在倍增同时合并线性基的题目。需要注意的是$p[x][i][j]$表示的是$x$这个点到$x$的$2^i$祖先的线性基第$j$位，并且这是不包含$x$这个点的(think why?),虽然更新包含不包含貌似没有什么区别，重复的值异或掉成$0$了。然后$LCA$暴力合并，记得把$LCA(u,v)$加入线性基内，因为这个点不会被爪巴到，然后就是线性基求最大值了。

代码

#include<bits/stdc++.h>
#define LL long long
#define Maxn 20005
using namespace std;
LL p[Maxn][15][65],f[Maxn][15],head[Maxn],n,q,luck[Maxn],cnt=0,Max_p[65],deep[Maxn];
struct edge{LL next,to;}e[Maxn<<1];
inline void read(LL &x)
{
    LL f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline void add(LL a,LL b){e[++cnt].next=head[a];e[cnt].to=b;head[a]=cnt;}
inline void insert(LL now,LL x,LL num)
{
    if (!num) return; 
    for (LL i=60;i>=0;i--)
    {
        if (!(num>>i&1)) continue;
        if (!p[now][x][i]){p[now][x][i]=num;return;}
        num^=p[now][x][i];
    }
    return;
}
inline void merge(LL a,LL x,LL b,LL y,LL c,LL z)
{
    for (int i=0;i<=60;i++) insert(a,x,p[b][y][i]);
    for (int i=0;i<=60;i++) insert(a,x,p[c][z][i]);
}
inline void insert2(LL num)
{
    if (!num) return; 
    for (LL i=60;i>=0;i--)
    {
        if (!(num>>i&1)) continue;
        if (!Max_p[i]){Max_p[i]=num;return;}
        num^=Max_p[i];
    }
    return;
}
inline void merge2(LL x,LL y)
{
    for (int i=0;i<=60;i++) insert2(p[x][y][i]);
}
inline void dfs1(LL now,LL fa)
{
    deep[now]=deep[fa]+1;
    f[now][0]=fa;
    insert(now,0,luck[fa]);
    for (LL i=1;i<=14;i++)
    {
        f[now][i]=f[f[now][i-1]][i-1];
        merge(now,i,now,i-1,f[now][i-1],i-1);
    }
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (v==fa) continue;
        dfs1(v,now);
    }
}
inline LL LCA(LL x,LL y)
{
    if (deep[x]<=deep[y]) swap(x,y);
    for (int i=14;i>=0;i--)
    if (deep[f[x][i]]>=deep[y]) 
    {
        merge2(x,i);
        x=f[x][i];
    }
    if (x==y) return x;
    for (int i=14;i>=0;i--)
    if (f[x][i]!=f[y][i]) 
    {
        merge2(x,i);
        x=f[x][i];
        merge2(y,i);
        y=f[y][i];
    }
    return f[x][0];
}
int main()
{
    read(n),read(q);
    for (LL i=1;i<=n;i++) read(luck[i]);
    for (LL x,y,i=1;i<n;i++)
    {
        read(x),read(y);
        add(x,y),add(y,x);
    }
    dfs1(1,0);
    while (q--)
    {
        LL x,y,ans=0;
        memset(Max_p,0,sizeof(Max_p));
        read(x),read(y);
        insert2(luck[LCA(x,y)]);
        insert2(luck[x]);
        insert2(luck[y]); 
        for (int i=60;i>=0;i--) if ((ans^Max_p[i])>ans) ans^=Max_p[i];
        cout<<ans<<endl;     
    }
    return 0;
}