Query on A Tree 题意：有一颗树，有n个节点，每个节点都有权值，有q次询问，每次询问以u为根的子树节点权值中异或x结果最大的值。 题解：首先解决u为根子树节点的问题，直接dfs序，解决异或，用字典树，但是同时用的话，就需要用可持久化字典树，其实就是前缀树。这题学习到一波可持久化字典树。
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #include<vector> using namespace std; const int maxn = 1e5+10; struct node { int sum[2]; int son[2]; }tr[maxn*32]; int tot = 0,cnt = 0; int L[maxn],R[maxn]; int rt[maxn],a[maxn]; vector<int>G[maxn]; int ans = 0; void build(int pre,int now,int val,int pos) { if(pos<0) return ; int tmp = !!(val&(1<<pos)); tr[now] = tr[pre]; tr[now].sum[tmp]++; tr[now].son[tmp] = ++cnt; build(tr[pre].son[tmp],tr[now].son[tmp],val,pos-1); } void dfs(int u) { L[u] = ++tot; rt[L[u]] = ++cnt; build(rt[L[u]-1],rt[L[u]],a[u],30); for(auto v:G[u]) dfs(v); R[u] = tot; } void qu(int pre,int now,int val,int pos) { if(pos<0) return ; int tmp = !!(val&(1<<pos)); if(tr[now].sum[!tmp]>tr[pre].sum[!tmp]) { ans += (1<<pos); qu(tr[pre].son[!tmp],tr[now].son[!tmp],val,pos-1); } else qu(tr[pre].son[tmp],tr[now].son[tmp],val,pos-1); } int main() { int n,q; while(~scanf("%d%d",&n,&q)) { memset(tr,0,sizeof(tr)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); G[i].clear(); } tot = 0; cnt = 0; for(int i=2;i<=n;i++) { int v; scanf("%d",&v); G[v].push_back(i); } dfs(1); for(int i=1;i<=q;i++) { ans = 0; int u,x; scanf("%d%d",&u,&x); qu(rt[L[u]-1],rt[R[u]],x,30); printf("%d\n",ans); } } }