题目链接
题意是给一棵树，每个点有点权，然后每次询问给一个子树和一个x，问子树上面所有的点中异或x的最大值是多少。
这个题目可以离线用字典树合并的方式，从叶子往根去合并，也可以用dfs序直接把子树转化为区间上的问题，然后用可持续化trie树去做。
可持续化trie树本质其实和主席树的建树方式差不多，动态建树且每一次新增一条链。然后当询问某一个子树的时候，通过dfs序把它变成一个区间，然后就是01字典树上面走走。从高到底看看这一位有没有与x相反的bit位，如果有还要判断是否在L到R的区间上。
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<time.h>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<iostream>
#include<stdlib.h>
using namespace std;
#define LONG long long
const int INF=0x3f3f3f3f;
const LONG MOD=1e9+ 7;
const double PI=acos(-1.0);
#define clrI(x) memset(x,-1,sizeof(x))
#define clr0(x) memset(x,0,sizeof x)
#define clr1(x) memset(x,INF,sizeof x)
#define clr2(x) memset(x,-INF,sizeof x)
#define EPS 1e-10
#define lson l , mid , rt<< 1
#define rson mid + 1 ,r , (rt<<1)+1
#define root 1, n , 1
const int MAXN = 140000 ;
int L[MAXN + 50 ] , R[MAXN + 50] ;
int TOT = 0;
int Root[MAXN + 50 ] ;
struct Trie
{
int next[2] ;
int sum ;
Init()
{
clrI(next) ;
sum = 0 ;
}
}trie[ (MAXN << 6 )+ (MAXN << 5)];
struct Edge
{
int next ,to ;
}edge[200100] ;
int head[MAXN] ;
int tot = 0 ;
int cnt = 0 ;
int V[MAXN] ;
int Rank[MAXN] ;
void Init()
{
tot = 0 ;
clrI(head) ;
cnt = 0 ;
TOT = 0;
}
void Add(int u ,int v)
{
edge[++tot].to = v;
edge[tot].next = head[u] ;
head[u] = tot ;
}
void Dfs(int pre ,int u)
{
L[u] = ++cnt ;
Rank[cnt] = u ;
for(int i = head[u] ;~i ; i = edge[i].next)
{
int v =edge[i].to ;
if(v == pre ) continue ;
Dfs(u , v) ;
}
R[u] = cnt ;
}
void Build(int x)
{
int now = 0 ;
for(int i = 31 ; i >= 0 ; -- i)
{
int p = (( x>>i ) & 1) ;
if(trie[now].next[p] == -1)
{
trie[now].next[p] = ++TOT ;
trie[TOT].Init() ;
}
now = trie[now].next[p] ;
trie[now].sum ;
}
}
int Insert(int x , int rt , int d )
{
TOT ++ ;
int now = TOT ;
trie[now] = trie[rt] ;
if( d== -1) return now ;
int p = ( (x>>d) & 1 ) ;
trie[now].next[p] = Insert( x , trie[now].next[p],d-1 ) ;
trie[trie[now].next[p]].sum ++ ;
return now ;
}
int Que(int x ,int L_rt,int R_rt)
{
int res = 0 ;
for(int i = 31 ; i >= 0 ; -- i)
{
int p = ((x>>i)&1) ;
if(trie[R_rt].next[p^1] == -1)
{
R_rt = trie[R_rt] .next[p] ;
L_rt = trie[L_rt] .next[p] ;
}
else
{
int tmp1 = trie[R_rt].next[p^1] ;
int tmp2 = trie[L_rt].next[p^1 ] ;
if(trie[tmp1].sum - trie[tmp2].sum > 0)
{
res += (1<<i) ;
R_rt = tmp1 ;
L_rt = tmp2 ;
}
else
{
R_rt = trie[R_rt].next[p] ;
L_rt = trie[L_rt].next[p] ;
}
}
}
return res ;
}
int main()
{
int n , q ;
while(cin >> n >> q)
{
Init() ;
for(int i = 1; i <= n ; ++ i)
scanf("%d",&V[i]) ;
int tmp ;
f or(int i= 1;i < n ; ++i)
{
scanf("%d",&tmp ) ;
Add(i + 1, tmp ) ;
Add(tmp , i + 1 ) ;
}
Dfs( -1 , 1) ;
for(int i= 1;i<= n ; ++ i)
trie[0].Init() ;
for(int i = 1 ;i<= n ; ++ i)
Build(V[Rank[ i ] ]) ;
Root[0] = 0 ;
for(int i = 1;i<= n ; ++ i)
Root[i] = Insert( V[Rank[i]] , Root[i-1 ] , 31) ;
int u , x;
int l ,r ;
int ans = 0 ;
while(q --)
{
scanf("%d%d",&u,&x) ;
l = L[u] - 1;
r = R[u] ;
ans = Que(x , Root[l] , Root[r]) ;
cout<<ans<<endl ;
}
for(int i = 0 ;i<= TOT ;++ i)
{
clrI( trie[i].next ) ;
trie[i].sum = 0 ;
}
}
return 0 ;
}