hdu6191 Query on A Tree(可持久化01字典树)

    xiaoxiao2022-09-22  5

    题目

    n(n<=1e5)个点,第i个点上有个权值vi(0<=vi<=1e9)

    q(q<=1e5)次询问,每次询问给出u和x,

    要求选择u的子树的一个节点y,使得y的权值异或x最大,

    输出这个最大值

    思路来源

    https://www.cnblogs.com/LQLlulu/p/9496426.html

    题解

    按dfs序将树压成线性序列,子树的权值就是一段连续的序列

    对线性序列建可持久化01字典树,

    询问u的子树的时候,就是[in[u],out[u]]这段序列对应的01字典树的最优解

    在该01字典树上贪心地跑,能反则反,被迫同则同,贪心地选

    注意开始建一条全0的链,但似乎题意没说可以不选???

    心得

    要习惯这种开若干个数组建数据结构的代码吧

    毕竟数组来模拟数据结构,往往无敌,不会被卡空间,也很少被卡时间

    学了一下可持久化01字典树,算是对可持久化结构理解更深了一步吧

    总之就是用的时候动态开点,查询时候两条链在同一节点一起向下跑

    代码

    #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<map> #include<vector> using namespace std; typedef long long ll; const int maxn=1e5+10; int n,q,par,u,x; int v[maxn]; int in[maxn],out[maxn],dfn; int ord[maxn]; vector<int>e[maxn]; int root[maxn]; int ch[maxn*33*2][2],cnt;//cnt用于动态开点 int num[maxn*33*2][2]; //01字典树 每个节点的值的出现个数 int id[maxn*33*2];//记录尾节点的值的pos void dfs(int u,int fa) { in[u]=++dfn; ord[dfn]=v[u]; for(int i=0;i<e[u].size();++i) { int v=e[u][i]; dfs(v,u);//单向边 直接搜 } out[u]=dfn; } void update(int pre,int cur,int x,int pos) { for(int i=30;i>=0;--i) { int j=x>>i&1; num[cur][j]+=num[pre][j]+1; num[cur][!j]+=num[pre][!j]; ch[cur][j]=++cnt; ch[cur][!j]=ch[pre][!j]; //现用现清 memset(ch[cnt],0,sizeof ch[cnt]); memset(num[cnt],0,sizeof num[cnt]); pre=ch[pre][j]; cur=ch[cur][j]; } id[cur]=pos;//记录链尾的下标 } int ask(int pre,int cur,int x) { for(int i=30;i>=0;--i) { int j=!(x>>i&1);//先取反的,不能取再取相同的 if(num[cur][j]-num[pre][j]>0) { cur=ch[cur][j]; pre=ch[pre][j]; } else { cur=ch[cur][!j]; pre=ch[pre][!j]; } } return id[cur]; } int main() { while(~scanf("%d%d",&n,&q)) { dfn=cnt=0; for(int i=1;i<=n;++i) { scanf("%d",&v[i]); e[i].clear(); } for(int i=2;i<=n;++i) { scanf("%d",&par); e[par].push_back(i); } dfs(1,-1); update(0,0,0,0);//建一个全0的链 for(int i=1;i<=n;++i) { root[i]=++cnt; update(root[i-1],root[i],ord[i],i); } for(int i=1;i<=q;++i) { scanf("%d%d",&u,&x); printf("%d\n",x^ord[ask(root[in[u]-1],root[out[u]],x)]); } } return 0; }

     

    最新回复(0)