题目vj链接

题面：

题意：
给定一棵树，点有点权。
m次询问，每次给定 x，y，z。求 x 到 y 的简单路径所经过的点的点权与 z 异或的最大值。

题解：
可持久化字典树。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
//#define max(x,y) ((x)>(y)?(x):(y))
//#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=100100;

int head[maxn],ver[maxn<<1],nt[maxn<<1],tot=1;
int d[maxn],f[maxn],son[maxn],si[maxn];
int rk[maxn],id[maxn],top[maxn],v[maxn],cnt=0;

int t[maxn*30][2],sum[maxn*30],root[maxn],res=0;
int n,m;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x,int fa)
{
    int maxson=0;
    si[x]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        f[y]=x;
        dfs1(y,x);
        si[x]+=si[y];
        if(si[y]>maxson) maxson=si[y],son[x]=y;
    }
}

void dfs2(int x,int t)
{
    top[x]=t;
    id[x]=++cnt;
    rk[cnt]=x;
    if(!son[x]) return ;
    dfs2(son[x],t);
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y!=son[x]&&y!=f[x])
            dfs2(y,y);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return id[x]>id[y]?y:x;
}

void init(void)
{
    tot=1,cnt=0,res=0;
    memset(head,0,sizeof(head));
    memset(son,0,sizeof(son));
}

int newnode(void)
{
    ++res;
    t[res][0]=t[res][1]=sum[res]=0;
    return res;
}

void _insert(int pre,int now,int val)
{
    for(int k=15;k>=0;k--)
    {
        int c=(val>>k)&1;
        t[now][c^1]=t[pre][c^1];
        t[now][c]=newnode();
        sum[t[now][c]]=sum[t[pre][c]]+1;
        pre=t[pre][c],now=t[now][c];
    }
}

int ask(int pre,int now,int val)
{
    int ans=0;
    for(int k=15;k>=0;k--)
    {
        int c=(val>>k)&1;
        if(sum[t[now][c^1]]-sum[t[pre][c^1]]>0)
        {
            now=t[now][c^1],pre=t[pre][c^1];
            ans+=(1<<k);
        }
        else now=t[now][c],pre=t[pre][c];
    }
    return ans;
}

void dfs(int x,int fa)
{
    root[x]=newnode();
    _insert(root[fa],root[x],v[x]);
    for(int i=head[x];i;i=nt[i])
    {
        if(ver[i]==fa) continue;
        dfs(ver[i],x);
    }
}

int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i]);

        int x,y,z;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }

        dfs1(1,0);
        dfs2(1,1);

        root[0]=newnode();
        dfs(1,0);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            int lcc=lca(x,y);
            printf("%d\n",max(ask(root[f[lcc]],root[x],z),ask(root[f[lcc]],root[y],z)));
        }
    }
    return 0;
}