题目
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;
}
