bzoj4568: [Scoi2016]幸运数字(LCA+线性基)

4568: [Scoi2016]幸运数字

题目：传送门

---

题解：

　　 好题！！！

　　 之前就看过，当时说是要用线性基...就没学

　　 填坑填坑：

　　 %%%线性基 && 神犇

　　 主要还是对于线性基的运用和LCA的灵活运用吧：

　　 设f[i][j][65]表示i到2^j-1的线性基集合

　　 跑LCA，边跑边暴力合并路径上的线性基咯，最后find_max一下xor的最大值就好啦

　　 槽点：注意^符号的优先级还有空间大小...有点恶心

---

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 struct node

 {

     int x,y,next;

 }a[];int len,last[];

 void ins(int x,int y)

 {

     len++;a[len].x=x;a[len].y=y;

     a[len].next=last[x];last[x]=len;

 }

 void add(LL *a,LL x)

 {

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

     {

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

         {

             if(!a[i]){a[i]=x;break;}

             x^=a[i];

         }

     }

 }

 void merge(LL *a,LL *b)

 {

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

         if(b[i])add(a,b[i]);

 }

 LL ans[],bin[],f[][][],dep[],fa[][];

 void pre_tree_node(int x)

 {

     for(int i=;bin[i]<=dep[x];i++)

     {

         fa[x][i]=fa[fa[x][i-]][i-];

         memcpy(f[x][i],f[x][i-],sizeof(f[x][i]));

         merge(f[x][i],f[fa[x][i-]][i-]);

     }

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(y!=fa[x][])

         {

             fa[y][]=x;

             dep[y]=dep[x]+;

             pre_tree_node(y);

         }

     }

 }

 void solve(int x,int y)

 {

     if(dep[x]<dep[y])swap(x,y);

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

         if(dep[fa[x][i]]>=dep[y])

             merge(ans,f[x][i]),x=fa[x][i];

     if(x==y){merge(ans,f[x][]);return ;}

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

         if(bin[i]<=dep[x] && fa[x][i]!=fa[y][i])

         {

             merge(ans,f[x][i]),merge(ans,f[y][i]);

             x=fa[x][i],y=fa[y][i];

         }

     merge(ans,f[x][]),merge(ans,f[y][]);

     merge(ans,f[fa[x][]][]);

     return ;

 }

 LL find_max()

 {

     LL sum=;

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

         if((sum^ans[i])>sum)

             sum^=ans[i];

     return sum;

 }

 int n,T;

 int main()

 {

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

     bin[]=1LL;for(int i=;i<=;i++)bin[i]=bin[i-]<<;

     len=;memset(last,,sizeof(last));

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

     {

         LL x;scanf("%lld",&x);

         add(f[i][],x);

     }

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

     {

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

         ins(x,y);ins(y,x);

     }

     fa[][]=;dep[]=;pre_tree_node();

     while(T--)

     {

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

         memset(ans,,sizeof(ans));

         solve(x,y);

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

     }

     return ;

 }