题意：
有一棵n个节点的树，每个节点都有一个值，m次查询，每次两个数x y表示以x为根的子树中哪个节点权值异或y得出的结果最大，求最大结果
离线
和线段树合并一样，在搜索过程中将多个字典树并在一起
每次查询遍历以当前子树的根为根的字典树
01字典树：http://blog.csdn.net/jaihk662/article/details/53914904
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<vector> #include<string.h> #include<stdlib.h> using namespace std; typedef struct { int x; int id; }Res; Res temp; typedef struct Trie { Trie *next[2]; }Trie; vector<int> G[100001]; vector<Res> Q[100001]; int val[100001], ans[100001]; Trie *root[100001]; void Update(Trie *q, int a) { int i, now; Trie *p = q; for(i=29;i>=0;i--) { now = 0; if(a&(1<<i)) now = 1; if(p->next[now]==NULL) { Trie *temp = new Trie; temp->next[0] = temp->next[1] = NULL; p->next[now] = temp; } p = p->next[now]; } } int Query(Trie *q, int a) { int i, now, bet; bet = 0; Trie *p = q; for(i=29;i>=0;i--) { now = 0; if(a&(1<<i)) now = 1; if(p->next[now^1]!=NULL) { p = p->next[now^1]; bet |= (1<<i); } else p = p->next[now]; } return bet; } Trie* Merge(Trie *p, Trie *q) { if(p==NULL) return q; if(q==NULL) return p; p->next[0] = Merge(p->next[0], q->next[0]); p->next[1] = Merge(p->next[1], q->next[1]); free(q); return p; } void Delete(Trie *q) { int i; if(q->next[0]) Delete(q->next[0]); if(q->next[1]) Delete(q->next[1]); free(q); } void Sech(int u) { int i, v; root[u] = new Trie; root[u]->next[1] = root[u]->next[0] = NULL; Update(root[u], val[u]); for(i=0;i<G[u].size();i++) { v = G[u][i]; Sech(v); root[u] = Merge(root[u], root[v]); } for(i=0;i<Q[u].size();i++) ans[Q[u][i].id] = Query(root[u], Q[u][i].x); } int main(void) { int n, q, i, x, y; while(scanf("%d%d", &n, &q)!=EOF) { memset(ans, 0, sizeof(ans)); for(i=1;i<=n;i++) { G[i].clear(); Q[i].clear(); scanf("%d", &val[i]); } for(i=2;i<=n;i++) { scanf("%d", &x); G[x].push_back(i); } for(i=1;i<=q;i++) { scanf("%d%d", &y, &x); temp.x = x, temp.id = i; Q[y].push_back(temp); } Sech(1); for(i=1;i<=q;i++) printf("%d\n", ans[i]); Delete(root[1]); } }
