洛谷P4592 [TJOI2018] 异或

树上路径与子树最大异或和问题。。。

想都不想一个树链剖分上去，变成序列问题。

区间最大异或和。。。这不板子么？

又是一个可持久化$TrieTrie$丢上去。

这个题就搞完了。

复杂度$O(32\times n{}_2(n))O(32\backslash times\; n\backslash log\_2(n))$，稳的不行。

（按理说我把$TrieTrie$树深度搞成$3232$也没啥问题，但样例过不去。。。可能是符号位的问题吧）

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
#define MAXM 62
using namespace std;
int n,q,c=1,d=1,num=0,bitsize=31,root[MAXN];
int head[MAXN],val[MAXN],deep[MAXN],size[MAXN],son[MAXN],fa[MAXN],top[MAXN],id[MAXN],pos[MAXN];
struct Tree{
    int next,to;
}tree[MAXN<<1];
struct Persistable_Trie{
    int data,son[2];
}a[MAXN*MAXM];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
	return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline void addedge(int x,int y){
    tree[c].to=y;tree[c].next=head[x];head[x]=c++;
    tree[c].to=x;tree[c].next=head[y];head[y]=c++;
}
void dfs1(int rt){
    son[rt]=0;size[rt]=1;
    for(int i=head[rt],will;i;i=tree[i].next){
        will=tree[i].to;
        if(!deep[will]){
            deep[will]=deep[rt]+1;
            fa[will]=rt;
            dfs1(will);
            size[rt]+=size[will];
            if(size[will]>size[son[rt]])son[rt]=will;
        }
    }
}
void dfs2(int rt,int f){
    id[rt]=d++;pos[id[rt]]=rt;top[rt]=f;
    if(son[rt])dfs2(son[rt],f);
    for(int i=head[rt],will;i;i=tree[i].next){
        will=tree[i].to;
        if(will!=son[rt]&&will!=fa[rt])dfs2(will,will);
    }
}
void insert(int v,int bit,int &rt){
    a[++num]=a[rt];rt=num;
    a[rt].data++;
    if(bit==-1)return;
    int k=v>>bit&1;
    insert(v,bit-1,a[rt].son[k]);
}
int query(int x,int bit,int i,int j){
    if(bit==-1)return 0;
    int k=(x>>bit&1);int s=0;
    if(a[a[j].son[k^1]].data>a[a[i].son[k^1]].data)s|=query(x,bit-1,a[i].son[k^1],a[j].son[k^1])|(1<<bit);
    else s|=query(x,bit-1,a[i].son[k],a[j].son[k]);
    return s;
}
int query_path(int u,int v,int w){
    int s=0;
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        s=max(s,query(w,bitsize,root[id[top[u]]-1],root[id[u]]));
        u=fa[top[u]];
    }
    if(deep[u]>deep[v])swap(u,v);
    s=max(s,query(w,bitsize,root[id[u]-1],root[id[v]]));
    return s;
}
void work(){
    int f,x,y,z;
    while(q--){
        f=read();x=read();
        if(f==1){
            z=read();
            printf("%d\n",query(z,bitsize,root[id[x]-1],root[id[x]+size[x]-1]));
        }
        else{
            y=read();z=read();
            printf("%d\n",query_path(x,y,z));
        }
    }
}
void init(){
    n=read();q=read();
    for(int i=1;i<=n;i++)val[i]=read();
    for(int i=1,x,y;i<n;i++){
        x=read();y=read();
        addedge(x,y);
    }
    deep[1]=1;
    dfs1(1);
    dfs2(1,1);
    root[0]=a[0].data=a[0].son[0]=a[0].son[1]=0;
    for(int i=1;i<=n;i++){
        root[i]=root[i-1];
        insert(val[pos[i]],bitsize,root[i]);
    }
}
int main(){
    init();
    work();
    return 0;
}