BZOJ5338：[TJOI2018]异或——题解

时间：2022-10-27 20:17:38

https://www.lydsy.com/JudgeOnline/problem.php?id=5338

现在有一颗以1为根节点的由n个节点组成的树，树上每个节点上都有一个权值vi。
现在有Q 次操作，操作如下:
1  x y    查询节点x的子树中与y异或结果的最大值
2 x y z    查询路径x到y上点与z异或结果最大值

HDU4757：Tree——题解

别的不想多说了，出原题不怕被骂吗……

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct trie{

    int son[],sum;

}tr[*N];

struct node{

    int to,nxt;

}e[N*];

int tot,a[N],rt[N*],pool,cnt,head[N],idx[N];

int dep[N],anc[N][],n,q,pos[N],id,size[N];

inline void add(int u,int v){

    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

void insert(int y,int &x,int k,int now){

    tr[x=++pool]=tr[y];

    tr[x].sum++;

    if(now<)return;

    bool p=k&(<<now);

    insert(tr[y].son[p],tr[x].son[p],k,now-);

    return;

}

int query(int nl,int nr,int k,int now){

    if(now<)return ;

    bool p=k&(<<now);

    int delta=tr[tr[nr].son[p^]].sum-tr[tr[nl].son[p^]].sum;

    if(delta>)return (<<now)+query(tr[nl].son[p^],tr[nr].son[p^],k,now-);

    else return query(tr[nl].son[p],tr[nr].son[p],k,now-);

}

void dfs(int u,int f){

    anc[u][]=f;pos[u]=++id;idx[id]=u;size[u]=;

    for(int k=;k<=;k++)

        anc[u][k]=anc[anc[u][k-]][k-];

    dep[u]=dep[f]+;

    insert(rt[f],rt[u],a[u],);

    for(int i=head[u];i;i=e[i].nxt){

        int v=e[i].to;

        if(v==f)continue;

        dfs(v,u);size[u]+=size[v];

    }

    return;

}

inline int LCA(int i,int j){

    if(dep[i]<dep[j])swap(i,j);

    for(int k=;k>=;k--){

        if(dep[anc[i][k]]>=dep[j])i=anc[i][k];

    }

    if(i==j)return i;

    for(int k=;k>=;k--){

        if(anc[i][k]!=anc[j][k])i=anc[i][k],j=anc[j][k];

    }

    return anc[i][];

}

int main(){

    n=read(),q=read();

    for(int i=;i<=n;i++)a[i]=read();

    for(int i=;i<n;i++){

        int u=read(),v=read();

        add(u,v);add(v,u);

    }

    dfs(,);

    for(int i=;i<=n;i++)insert(rt[i+n],rt[i+n+],a[idx[i]],);

    for(int i=;i<=q;i++){

        int op=read();

        if(op==){

            int x=read(),y=read();

            int l=pos[x],r=l+size[x]-;

            printf("%d\n",query(rt[l+n],rt[r+n+],y,));

        }else{

            int x=read(),y=read(),z=read();

            int lca=LCA(x,y),f=anc[lca][];

            printf("%d\n",max(query(rt[f],rt[x],z,),query(rt[f],rt[y],z,)));

        }

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

相关文章