小圆前辈的异或树

题目链接：https://ac.nowcoder.com/acm/contest/15332/J

题目大意：

一棵树棵树，求 。

定义：为到最短路径所经过的点的权值异或和

思路：

首先我们可以令一个根节点，处理从到的异或和，这样,我们只需要知道，和的就能求得其，但枚举肯定超时，这是就需要用到启发式合并优雅的枚举（雾

但仅仅启发式合并貌似还是不够的，因为枚举轻儿子的节点u时，我们貌似不能很快的找到对应的点，得到, 这时我们就需要建一颗字典树就能完美的解决这问题了。

时间复杂度大概就是

代码实现：

#include <iostream>
#include <vector>
using namespace std;
const int N=1e5+7;
struct Edge{int to,next;}e[2*N];
int n,a[N],pre[N],son[N],sz[N],tire[24*N][2];
vector <int> ho;
int head[N],idx,tot;
int flag,Ans;
void add(int u,int v){
    e[++tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void insert(int x){
    int p=0;
    for(int i=23;i>=0;i--){
        int ch=x>>i &1;
        if(!tire[p][ch]) tire[p][ch]=++idx;
        p=tire[p][ch];
    }
}

int qry(int x){
    int p=0;
    int res=0;
    for(int i=23;i>=0;i--){
        int ch=x>>i &1;
        if(tire[p][ch^1]){
            res+=1<<i;
            p=tire[p][ch^1];
        }else{
            p=tire[p][ch^0];
        }

    }
    return res;
}
void del(){
    for(int i=0;i<=idx;i++){
        tire[i][0]=0;
        tire[i][1]=0;
    }
    idx=0;
}
void add(){
    for(int i=0;i<ho.size();i++){
        insert(ho[i]);
    }
    ho.clear();
}

void ikuzo(int u,int fa,int xo){
    xo^=a[u];
    pre[u]=xo;
    sz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        ikuzo(v,u,xo);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]){
            son[u]=v;
        }
    }
}
void dfs(int u,int fa,int lca){
    Ans=max(Ans,qry(pre[u]^a[lca]));
    ho.push_back(pre[u]);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u,lca);
    }
}

void count(int u,int fa){
    Ans=max(Ans,qry(pre[u]^a[u]));
    insert(pre[u]);
    //cout<<"In "<<u<<" "<<pre[u]<<endl;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||v==flag) continue;
        dfs(v,u,u);
        add();
    }
}
void dsu(int u,int fa,int keep){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||v==son[u]) continue;
        dsu(v,u,1);
    }    
    if(son[u]){
        dsu(son[u],u,0);
        flag=son[u];
    }
    count(u,fa);
    flag=0;
    if(keep){
        del();
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n-1;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v),add(v,u);
    }
    ikuzo(1,-1,0);
    dsu(1,-1,0);
    printf("%d\n",Ans);
}