[BZOJ5338][TJOI2018]xor(可持久化Trie)

可持久化Trie模板题。

建两种可持久化Trie，每个点两棵，一棵对DFS求前缀和，一棵对祖先求前缀和。

或者树剖，不好写多少还多个log。

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])

 using namespace std;

 const int N=;

 int n,u,v,Q,x,y,z,op,nd,tim,cnt,t,a[N],rt1[N],rt2[N],fa[N][];

 int h[N],to[N<<],nxt[N<<],L[N],R[N],dep[N],ch[N*][],d[N*];

 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }

 void ins(int &x,int y,int k){

     int tmp=++nd; x=tmp;

     for (int i=; ~i; i--){

         ch[x][]=ch[y][]; ch[x][]=ch[y][]; d[x]=d[y]+;

         int t=(k>>i)&; ch[x][t]=++nd; x=ch[x][t]; y=ch[y][t];

     }

     d[x]=d[y]+; x=tmp;

 }

 int cal1(int x,int y,int k){

     int res=;

     for (int i=; ~i; i--){

         int t=((k>>i)&)^;

         if (d[ch[y][t]]-d[ch[x][t]]) res^=<<i,x=ch[x][t],y=ch[y][t];

             else x=ch[x][t^],y=ch[y][t^];

     }

     return res;

 }

 int cal2(int s1,int s2,int s3,int s4,int k){

     int res=;

     for (int i=; ~i; i--){

         int t=((k>>i)&)^;

         if (d[ch[s1][t]]+d[ch[s2][t]]-d[ch[s3][t]]-d[ch[s4][t]])

             res^=<<i,s1=ch[s1][t],s2=ch[s2][t],s3=ch[s3][t],s4=ch[s4][t];

         else s1=ch[s1][t^],s2=ch[s2][t^],s3=ch[s3][t^],s4=ch[s4][t^];

     }

     return res;

 }

 int Lca(int u,int v){

     if (dep[u]<dep[v]) swap(u,v);

     int t=dep[u]-dep[v];

     for (int i=; ~i; i--) if (t&(<<i)) u=fa[u][i];

     if (u==v) return u;

     for (int i=; ~i; i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];

     return fa[u][];

 }

 void dfs(int x){

     rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];

     L[x]=++tim; ins(rt1[tim],rt1[tim-],a[x]);

     For(i,x) if ((k=to[i])!=fa[x][])

         fa[k][]=x,ins(rt2[k],rt2[x],a[k]),dep[k]=dep[x]+,dfs(k);

     R[x]=tim;

 }

 int main(){

     freopen("bzoj5338.in","r",stdin);

     freopen("bzoj5338.out","w",stdout);

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

     rep(i,,n) scanf("%d",&a[i]);

     rep(i,,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);

     dfs();

     while (Q--){

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

         if (op==) printf("%d\n",cal1(rt1[L[x]-],rt1[R[x]],y));

         else scanf("%d",&z),t=Lca(x,y),printf("%d\n",cal2(rt2[x],rt2[y],rt2[t],rt2[fa[t][]],z));

     }

     return ;

 }