题意：给你一棵有根树，树上每个节点有一个值，每次询问以u为根节点的子树异或上x的最大值。
题解：按照dfs序建关于数字的二进制可持久化字典树就好了= =
AC代码：
#include<stdio.h> #include<vector> #include<string.h> #define N 100005 using namespace std; int a[N]; vector<int>vt[N]; int tree[N*35][2],son[N*35][2],root[N],tot,index; int tou[N],la[N]; void build(int last,int cur,int num,int pos) { if(pos<0)return ; int temp=(num&(1<<pos))>0; tree[cur][temp]=tree[last][temp]+1; tree[cur][temp^1]=tree[last][temp^1]; son[cur][temp^1]=son[last][temp^1]; build(son[last][temp],son[cur][temp]=++tot,num,pos-1); } void dfs(int u) { la[u]=++index; build(root[la[u]-1],root[la[u]]=++tot,a[u],30); for(int i=0;i<vt[u].size();i++) { int to=vt[u][i]; dfs(to); } tou[u]=index; } int query(int last,int cur,int num,int sum,int pos) { if(pos<0)return sum; int temp=!!(num&(1<<pos)); if(tree[cur][temp^1]-tree[last][temp^1]>0)return query(son[last][temp^1],son[cur][temp^1],num,sum|(1<<pos),pos-1); else return query(son[last][temp],son[cur][temp],num,sum,pos-1); } int main() { int n,q; while(~scanf("%d%d",&n,&q)) { memset(son,0,sizeof(son)); memset(tree,0,sizeof(tree)); memset(root,0,sizeof(root)); tot=index=0; for(int i=0;i<100005;i++)vt[i].clear(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=2;i<=n;i++) { int u; scanf("%d",&u); vt[u].push_back(i); } dfs(1); while(q--) { int u,x; scanf("%d%d",&u,&x); printf("%d\n",query(root[la[u]-1],root[tou[u]],x,0,30)); } } }
