题意：有一棵树，树根为1，树上的每个结点都有一个数字x。给出Q组询问，每组询问有两个值u,x，代表询问以结点u为根的子树中的某一个数与x的最大异或值。
解法一：dfs序+可持久化字典树。看到子树询问，首先要想到dfs序啦。可以对所有结点按dfs序依次建立可持久化的字典树，字典树上的每个结点除了要保存它的后继结点以外，还要保存这个结点出现的次数num。询问结点u时，对[bg[u],ed[u]]上的字典树的num做差，字典树上剩下的num>0的结点即为可行状态，然后按普通的字典树的查询方法查询就是了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
const int M=;
int n,Q,head[N],nxt[N],to[N],val[N],nEdge;
int rt[N],num[N*],go[N*][],nnode;
int bg[N],ed[N],tot;
void AddEdge(int u,int v) {
nxt[nEdge]=head[u],to[nEdge]=v,head[u]=nEdge++;
} int update(int v,int x,int bit) {
int u=++nnode;
num[u]=num[v]+;
if(bit<)return u;
int t=(x>>bit)&;
go[u][t]=update(go[v][t],x,bit-);
go[u][t^]=go[v][t^];
return u;
} void dfs(int u) {
bg[u]=++tot;
rt[tot]=update(rt[tot-],val[u],M);
for(int e=head[u]; ~e; e=nxt[e]) {
int v=to[e];
dfs(v);
}
ed[u]=tot;
} int query(int u,int v,int x,int bit,int now) {
if(bit<)return now;
int t=(x>>bit)&;
if(go[u][t^]-go[v][t^]>)
return query(go[u][t^],go[v][t^],x,bit-,now|(<<bit));
else return query(go[u][t],go[v][t],x,bit-,now);
} int main() {
while(scanf("%d%d",&n,&Q)==) {
memset(head,-,sizeof head);
nEdge=nnode=tot=;
for(int i=; i<=n; ++i)scanf("%d",&val[i]);
for(int i=; i<=n; ++i) {
int u;
scanf("%d",&u);
AddEdge(u,i);
}
rt[]=go[][]=go[][]=num[]=;
dfs();
while(Q--) {
int u,x;
scanf("%d%d",&u,&x);
printf("%d\n",query(rt[ed[u]],rt[bg[u]-],x,M,));
}
}
return ;
}
解法二：离线+字典树合并。可以自底而上来回答询问，每回答完一个结点下的所有子节点的询问，就将这个结点的字典树与它所有子节点的字典树合并。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
const int M=;
int n,Q,head[N],nxt[N],to[N],val[N],nEdge;
int rt[N],go[N*][],nnode,ans[N];
struct QUERY {
int x,i;
};
vector<QUERY> qr[N];
void AddEdge(int u,int v) {
nxt[nEdge]=head[u],to[nEdge]=v,head[u]=nEdge++;
} int build(int x,int bit) {
int u=++nnode;
if(bit<)return u;
int t=(x>>bit)&;
go[u][t]=build(x,bit-);
go[u][t^]=;
return u;
} int Merge(int u,int v,int bit) {
if(!u)return v;
if(!v)return u;
if(bit<)return u;
go[u][]=Merge(go[u][],go[v][],bit-);
go[u][]=Merge(go[u][],go[v][],bit-);
return u;
} int query(int u,int x,int bit,int now) {
if(bit<)return now;
int t=(x>>bit)&;
if(go[u][t^])
return query(go[u][t^],x,bit-,now|(<<bit));
else return query(go[u][t],x,bit-,now);
} void dfs(int u) {
for(int e=head[u]; ~e; e=nxt[e]) {
int v=to[e];
dfs(v);
}
for(int e=head[u]; ~e; e=nxt[e]) {
int v=to[e];
rt[u]=Merge(rt[u],rt[v],M);
}
for(int i=; i<qr[u].size(); ++i) {
ans[qr[u][i].i]=query(rt[u],qr[u][i].x,M,);
}
} int main() {
while(scanf("%d%d",&n,&Q)==) {
memset(head,-,sizeof head);
nEdge=nnode=;
for(int i=; i<=n; ++i)qr[i].clear();
for(int i=; i<=n; ++i)scanf("%d",&val[i]);
for(int i=; i<=n; ++i) {
int u;
scanf("%d",&u);
AddEdge(u,i);
}
for(int i=; i<=n; ++i)rt[i]=build(val[i],M);
for(int i=; i<Q; ++i) {
int u,x;
scanf("%d%d",&u,&x);
qr[u].push_back({x,i});
}
dfs();
for(int i=; i<Q; ++i)printf("%d\n",ans[i]);
}
return ;
}
还有一种解法是“可持久化字典树合并”，即父结点继承所有子结点的字典树，继承的方式与字典树合并一样，只不过把两棵树的公共部分开新结点就好，也是在线的，但空间消耗较大。
#define FRER() freopen("i.txt","r",stdin)
#define FREW() freopen("o.txt","w",stdout)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
const int M=;
int n,Q,head[N],nxt[N],to[N],val[N],nEdge;
int rt[N],go[N*][],nnode,ans[N];
void AddEdge(int u,int v) {
nxt[nEdge]=head[u],to[nEdge]=v,head[u]=nEdge++;
}
int build(int x,int bit) {
int u=++nnode;
if(bit<)return u;
int t=(x>>bit)&;
go[u][t]=build(x,bit-);
go[u][t^]=;
return u;
}
int Merge(int u,int v,int bit) {
if(!u)return v;
if(!v)return u;
if(bit<)return u;
int w=++nnode;
go[w][]=Merge(go[u][],go[v][],bit-);
go[w][]=Merge(go[u][],go[v][],bit-);
return w;
}
int query(int u,int x,int bit,int now) {
if(bit<)return now;
int t=(x>>bit)&;
if(go[u][t^])
return query(go[u][t^],x,bit-,now|(<<bit));
else return query(go[u][t],x,bit-,now);
}
void dfs(int u) {
for(int e=head[u]; ~e; e=nxt[e]) {
int v=to[e];
dfs(v);
}
for(int e=head[u]; ~e; e=nxt[e]) {
int v=to[e];
rt[u]=Merge(rt[u],rt[v],M);
}
}
int main() {
while(scanf("%d%d",&n,&Q)==) {
memset(head,-,sizeof head);
nEdge=nnode=;
for(int i=; i<=n; ++i)scanf("%d",&val[i]);
for(int i=; i<=n; ++i) {
int u;
scanf("%d",&u);
AddEdge(u,i);
}
for(int i=; i<=n; ++i)rt[i]=build(val[i],M);
dfs();
for(int i=; i<Q; ++i) {
int u,x;
scanf("%d%d",&u,&x);
printf("%d\n",query(rt[u],x,M,));
}
}
return ;
}