题目
给出一棵有 n 个结点的树, 树根是 1, 每个结点给出一个 value. 然后给出 q 个询问, 每个询问给出两个整数 u 和 x, 你要在以 u 结点为根的子树中找出一个结点 v, 使得 val[v] xor x 最大, 并输出这个最大值
分析
显而易见的可持久化字典树, 只不过这次每次查询不是查询一个区间, 而是查询一棵子树. 那么也很简单, 我们只要预处理出 dfs 序然后找出每个结点以它为根的子树在 dfs 序中的区间. 然后以这个区间建可持久化字典树就可以了.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int maxn=100000+10;
- int val[maxn];
- int head[maxn],to[maxn],Next[maxn];
- int n,q,sz;
- void add_edge(int a,int b){
- ++sz;
- to[sz]=b;Next[sz]=head[a];head[a]=sz;
- }
- int order[maxn],L[maxn],R[maxn],num;
- void dfs(int u,int fa){
- num++;
- order[num]=val[u];
- L[u]=num;
- for(int i=head[u];i!=-1;i=Next[i]){
- int v=to[i];
- if(v!=fa)
- dfs(v,u);
- }
- R[u]=num;
- }
- int ch[maxn*2*33][2],root[maxn],sum[maxn*2*33][2],cnt,val_t[2*maxn*33];
- void update(int x,int y,int a,int ID){
- root[x]=++cnt;x=root[x];
- for(int i=31;i>=0;i--){
- int id=(a>>i)&1;
- sum[x][id]+=sum[y][id]+1;
- sum[x][!id]+=sum[y][!id];
- ch[x][!id]=ch[y][!id];
- ch[x][id]=++cnt;
- memset(ch[cnt],0,sizeof(ch[cnt]));
- val_t[cnt]=0;
- x=ch[x][id];y=ch[y][id];
- }
- val_t[x]=ID;
- }
- int query(int x,int y,int a){
- for(int i=31;i>=0;i--){
- int id=(a>>i)&1;
- if(sum[x][!id]-sum[y][!id]){
- x=ch[x][!id],y=ch[y][!id];
- }else{
- x=ch[x][id],y=ch[y][id];
- }
- }
- return val_t[x];
- }
- int main(){
- while(scanf("%d%d",&n,&q)!=EOF){
- sz=0;
- cnt=0;
- memset(head,-1,sizeof(head));
- memset(sum,0,sizeof(sum));
- for(int i=1;i<=n;i++){
- scanf("%d",&val[i]);
- }
- for(int i=2;i<=n;i++){
- int a;
- scanf("%d",&a);
- add_edge(a,i);
- }
- num=0;
- dfs(1,-1);
- // for(int i=1;i<=n;i++)
- // printf("%d",order[i]);
- // printf("\n");
- update(0,0,0,0);
- for(int i=1;i<=n;i++){
- update(i,root[i-1],order[i],i);
- }
- int u,x;
- for(int i=1;i<=q;i++){
- scanf("%d%d",&u,&x);
- printf("%d\n",order[query(root[R[u]],root[L[u]-1],x)]^x);
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2732248.html