洛谷P4592 [TJOI2018]异或

图文无关

出道裸题觉得简单了非要上树系列。

如果没在树上就是裸的可持久化字典树，在树上写个树剖就完事了。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[200005];
struct Trie {
    int vis[2],val;
} tree[3200005];
int cnt,ecnt,dfsord,head[100005],n,m,a,b,c,d,s[100005],rt[100005],snew[100005];
int fa[100005],deep[100005],siz[100005],son[100005],id[100005],top[100005];

inline void add(int u,int v)
{
    edge[++ecnt].to=v;
    edge[ecnt].next=head[u];
    head[u]=ecnt;
}

inline void build(int x,int now,int last)
{
    for (int i=30;i>=0;i--)
    {
        tree[now].val=tree[last].val+1;
        int nxt=(x>>i)&1;
        if (!tree[now].vis[nxt]) tree[now].vis[nxt]=++cnt;
        tree[now].vis[nxt^1]=tree[last].vis[nxt^1];
        now=tree[now].vis[nxt];
        last=tree[last].vis[nxt];
    }
    tree[now].val=tree[last].val+1;
}

inline int query(int x,int now1,int now2)
{
    int ans=0;
    for (int i=30;i>=0;i--)
    {
        int nxt=(x>>i)&1;
        if (tree[tree[now1].vis[nxt^1]].val!=tree[tree[now2].vis[nxt^1]].val)
        {
            now1=tree[now1].vis[nxt^1];
            now2=tree[now2].vis[nxt^1];
            ans+=(1<<i);
        }
        else
        {
            now1=tree[now1].vis[nxt];
            now2=tree[now2].vis[nxt];
        }
    }
    return ans;
}

void dfs1(int x,int f,int dep)
{
    fa[x]=f;
    deep[x]=dep;
    siz[x]=1;
    int mx=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs1(y,x,dep+1);
        siz[x]+=siz[y];
        if (siz[x]>mx)
        {
            mx=siz[x];
            son[x]=y;
        }
    }
}

void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++dfsord;
    snew[dfsord]=s[x];
    if (!son[x]) return;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa[x] || y==son[x]) continue;
        dfs2(y,y);
    }
}

inline int qRange(int u,int v,int w)
{
    int ans=0;
    while (top[u]!=top[v])
    {
        if (deep[top[u]]<deep[top[v]]) swap(u,v);
        ans=max(ans,query(w,rt[id[top[u]]-1],rt[id[u]]));
        u=fa[top[u]];
    }
    if (deep[u]>deep[v]) swap(u,v);
    ans=max(ans,query(w,rt[id[u]-1],rt[id[v]]));
    return ans;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for (int i=1;i<=n;i++) 
    {
        rt[i]=++cnt;
        build(snew[i],rt[i],rt[i-1]);
    }
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        if (a==1) printf("%d\n",query(c,rt[id[b]-1],rt[id[b]+siz[b]-1]));
        else
        {
            d=read();
            printf("%d\n",qRange(b,c,d));
        }
    }
    return 0;
}