A 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个

幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览 A 国。旅行者计划

乘飞机降落在 x 号城市，沿着 x 号城市到 y 号城市之间那条唯一的路径游览，最终从 y 城市起飞离开 A 国。

在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸

运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，

游览者拍了 3 张照片，幸运值分别是 5，7，11，那么最终保留在自己身上的幸运值就是 9（5 xor 7 xor 11）。

有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 5 

和 11 ，可以保留的幸运值为 14 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中

可以保留的最大幸运值是多少。

 

第一行包含 2 个正整数 n ，q，分别表示城市的数量和旅行者数量。第二行包含 n 个非负整数，其中第 i 个整

数 Gi 表示 i 号城市的幸运值。随后 n-1 行，每行包含两个正整数 x ，y，表示 x 号城市和 y 号城市之间有一

条道路相连。随后 q 行，每行包含两个正整数 x ，y，表示这名旅行者的旅行计划是从 x 号城市到 y 号城市。N

<=20000,Q<=200000,Gi<=2^60

 

 

4 2

11 5 7 9

1 2

1 3

1 4

2 3

1 4

14

11

题目意思：
　　　　题意很好理解，在一棵树，每个点都有权值，然后每次问，u--->v的xor的最大值，可以xor点
　　　　权或者不xor。
题解：
　　　　暴力合并线性基，线段树维护+树链剖分吧。

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #define ll long long

 #define N 20007

 using namespace std;

 int n,bh,m;

 int cnt,head[N],next[N*],rea[N*];

 int deep[N],pos[N],siz[N],bel[N],fa[N];

 ll pre[N],a[N];

 struct xxj

 {

     ll a[];

 }tr[N<<],res;

 void add(int u,int v)

 {

     next[++cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

 }

 void dfs_init(int u,int fq)

 {

     siz[u]=;

     for (int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if (v==fq) continue;

         deep[v]=deep[u]+,fa[v]=u;

         dfs_init(v,u);

         siz[u]+=siz[v];

     }

 }

 void dfs_make(int u,int chain)

 {

     int k=;

     pos[u]=++bh,bel[u]=chain,pre[bh]=a[u];

     for (int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if (deep[v]>deep[u]&&siz[v]>siz[k]) k=v;

     }

     if (k==) return;

     dfs_make(k,chain);

     for (int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if (deep[v]>deep[u]&&v!=k) dfs_make(v,v);

     }

 }

 void merge(xxj &x,xxj &y,xxj &z)

 {

     x=y;

     for (int i=;i>=;i--)

     {

         if (z.a[i])

         {

             ll num=z.a[i];

             for (int j=;j>=;j--)

                 if (num&(1ll<<j))

                     if (!x.a[j])

                     {

                         x.a[j]=num;

                         break;

                     }

                     else num^=x.a[j];

         }

     }

 }

 void build_tree(int l,int r,int p)

 {

     if (l==r)

     {

         ll x=pre[l];

         for (int i=;i>=;i--)

             if (x&(1ll<<i))

                 if (!tr[p].a[i])

                 {

                     tr[p].a[i]=x;

                     break;

                 }

                 else x^=tr[p].a[i];

         return;

     }

     int mid=(l+r)>>;

     build_tree(l,mid,p<<),build_tree(mid+,r,p<<|);

     merge(tr[p],tr[p<<],tr[p<<|]);

 }

 void query(int p,int l,int r,int x,int y)

 {

     if (l==x&&r==y)

     {

         merge(res,res,tr[p]);

         return;

     }

     int mid=(l+r)>>;

     if (y<=mid) query(p<<,l,mid,x,y);

     else if (x>mid) query(p<<|,mid+,r,x,y);

     else query(p<<,l,mid,x,mid),query(p<<|,mid+,r,mid+,y);

 }

 void solve_query(int x,int y)

 {

     while(bel[x]!=bel[y])

     {

         if (deep[bel[x]]<deep[bel[y]]) swap(x,y);

         query(,,n,pos[bel[x]],pos[x]);

         x=fa[bel[x]];

     }

     if (deep[x]>deep[y]) swap(x,y);

     query(,,n,pos[x],pos[y]);

 }

 int main()

 {

     memset(head,-,sizeof(head));

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++)

         scanf("%lld",&a[i]);

     for (int i=,x,y;i<n;i++)

     {

         scanf("%d%d",&x,&y);

         add(x,y),add(y,x);

     }

     dfs_init(,-);

     dfs_make(,);

     build_tree(,n,);

     for(int i=,x,y;i<=m;i++)

     {

         scanf("%d%d",&x,&y);ll ans=;

         memset(res.a,,sizeof(res.a));

         solve_query(x,y);

         for (int i=;i>=;i--)

             if ((ans^res.a[i])>ans) ans^=res.a[i];

         printf("%lld\n",ans);

     }

 }