Problem Description
Monkey A lives on a tree, he always plays on this tree.
One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.
Monkey A gave a value to each node on the tree. And he was curious about a problem.
The problem is how large the xor result of number x and one node value of label y can be, when giving you a non-negative integer x and a node label u indicates that node y is in the subtree whose root is u(y can be equal to u).
Can you help him?
Input
There are no more than 6 test cases.
For each test case there are two positive integers n and q, indicate that the tree has n nodes and you need to answer q queries.
Then two lines follow.
The first line contains n non-negative integers V1,V2,⋯,Vn, indicating the value of node i.
The second line contains n-1 non-negative integers F1,F2,⋯Fn−1, Fi means the father of node i+1.
And then q lines follow.
In the i-th line, there are two integers u and x, indicating that the node you pick should be in the subtree of u, and x has been described in the problem.
2≤n,q≤105
0≤Vi≤109
1≤Fi≤n, the root of the tree is node 1.
1≤u≤n,0≤x≤109
Output
For each query, just print an integer in a line indicating the largest result.
Sample Input
2 2
1 2
1
1 3
2 1
Sample Output
2
3
题目大意:一棵树,每一个节点有一个权值vi,有M组询问(u,x)表示求u的子树内某一个节点y,使得\(v_y xor x\) 最大
解题报告:对于子树询问，一般转化为区间求解，此题没有修改，直接上莫队，对于xor操作取max，显然这是trie树的基本操作，所以此题就是个trie树维护的莫队,指针的移动对应trie树中的插入和删除.
对于询问，我们在trie树中查询，我们尽量往和x相反的方向走即可
复杂度：\(O(n\sqrt{n}log_2n)\)
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e5+5,M=6e6+5,maxdep=30;
int gi(){
int str=0;char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
struct node{
int l,r,s;
}t[M];
int tot=0,w[35],root=0,n,Q,val[N],nxt[N<<1],to[N<<1],head[N];
int num=0,blc;
void link(int x,int y){
nxt[++num]=head[x];to[num]=y;head[x]=num;
}
void insert(int &rt,int x,int d,int to){
if(!rt)rt=++tot;
if(d==-1){
t[rt].s+=to;return ;
}
if(x&w[d])insert(t[rt].r,x,d-1,to);
else insert(t[rt].l,x,d-1,to);
t[rt].s=t[t[rt].l].s+t[t[rt].r].s;
}
int query(int &rt,int x,int d){
if(!rt || d==-1)return 0;
if(x&w[d]){
if(t[t[rt].l].s)return query(t[rt].l,x,d-1)+w[d];
return query(t[rt].r,x,d-1);
}
else{
if(t[t[rt].r].s)return query(t[rt].r,x,d-1)+w[d];
return query(t[rt].l,x,d-1);
}
}
int DFN=0,L[N],R[N],ans[N],dfn[N];
void dfs(int x,int last){
int u;L[x]=++DFN;dfn[DFN]=x;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last)continue;
dfs(u,x);
}
R[x]=DFN;
}
struct Ques{
int l,r,x,bs,id;
bool operator <(const Ques &pp)const{
if(bs!=pp.bs)return bs<pp.bs;
return r<pp.r;
}
}q[N];
void add(int i){
insert(root,val[dfn[i]],maxdep,1);
}
void delet(int i){
insert(root,val[dfn[i]],maxdep,-1);
}
void Clear(){
num=0;tot=0;DFN=0;root=0;memset(head,0,sizeof(head));
memset(t,0,sizeof(t));
}
void work()
{
Clear();
int x,y;
blc=sqrt(n)+1;
for(int i=1;i<=n;i++)val[i]=gi();
for(int i=2;i<=n;i++){
x=gi();
link(x,i);link(i,x);
}
dfs(1,1);
for(int i=1;i<=Q;i++){
x=gi();y=gi();
q[i].l=L[x];q[i].r=R[x];q[i].x=y;
q[i].bs=q[i].l/blc;q[i].id=i;
}
sort(q+1,q+Q+1);
int l=1,r=0;
for(int i=1;i<=Q;i++){
while(r<q[i].r)r++,add(r);
while(l>q[i].l)l--,add(l);
while(r>q[i].r)delet(r),r--;
while(l<q[i].l)delet(l),l++;
ans[q[i].id]=query(root,q[i].x,maxdep);
}
for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
}
int main()
{
w[0]=1;for(int i=1;i<=maxdep;i++)w[i]=w[i-1]<<1;
while(~scanf("%d%d",&n,&Q))
work();
return 0;
}