CF840E In a Trap

题意：给你一棵节点带权树。q个询问，每次询问u到v的路径上max(a[i]^dis(i,v))?

保证u是v的祖先，i是u->v路径上的点。n,ai<=5e4。

标程：

 #include<bits/stdc++.h>

 using namespace std;

 int read()

 {

    int x=,f=;char ch=getchar();

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

    return x*f;

 }

 const int N=;

 int cnt,n,q,u,v,a[N],dep[N],head[N],fa[N],sc,son[][],t,c,now,sum,f[N][],jp[N],ans,base;

 struct node{int to,next;}num[N*];

 void add(int x,int y)

 {num[++cnt].to=y;num[cnt].next=head[x];head[x]=cnt;}

 void dfs(int x)

 {

     for (int i=head[x];i;i=num[i].next)

       if (num[i].to!=fa[x]) {

         dep[num[i].to]=dep[x]+;

           fa[num[i].to]=x;

           dfs(num[i].to);

       }

 }

 int main()

 {

     n=read();q=read();

     for (int i=;i<=n;i++) a[i]=read();

     for (int i=;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);

     dfs();

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

       if (dep[i]>=)

       {

          int x=i;sc=;son[][]=son[][]=;

          for (int j=;j<;j++,x=fa[x])//add_Trie

          {

            t=a[x]^j;now=;

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

            {

                c=(t>>k)&;

                if (!son[now][c]) son[now][c]=++sc,son[sc][]=son[sc][]=;

                now=son[now][c];

             }

          }

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

          {

              t=j<<;now=sum=;

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

              {

                  c=(t>>k)&;

                  if (son[now][c^]) now=son[now][c^],sum+=(<<k);else now=son[now][c];

             }

              f[i][j]=sum;

          }

          jp[i]=x;

     }

    while (q--)

    {

        u=read();v=read();ans=base=;

        for (;dep[v]-dep[u]>=;v=jp[v]) ans=max(ans,f[v][base]),base++;

        for (base=base*;v!=fa[u];v=fa[v],base++) ans=max(ans,a[v]^base);

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

     }

    return ;

 }

题解：分块+Trie

异或性质：比如需要异或x，那么^(x&255)^((x>>8)<<8)等价。拆数异或值不变。

对于每个点到根的链，每256个分一个块。

每个点x保存f[x][i]表示从x以上256个点的块中max(a[j]^dis(x,j)^(i<<8))。容易用字典树处理出所有i的最大异或值。

查询的时候按照块跳。统计max(f[v][base])，每次base++。

时间复杂度O(q*256+n*256*logn)。