一道广西邀请赛的题，赛场上想到了trie合并，但是没写过，算不清时间复杂度。于是迟迟没下去手 下来之后瞅了瞅感觉很简单啊，用递归+指针写了写，结果MLE+RE到绝望。 最后改成了非递归终于勉强过了orz。。。
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6191
题意：
给一棵树，树上每个节点有权值，有q次询问，问这个点及其子树的点任意一个点的值与某个值x进行xor运算，可以的出来的最大值是多少。
思路：
将全部询问离线，从子节点到根节点一个个询问。然后每次回溯回来的时候，将子树的01trie启发式合并一下。一直重复这样的操作就可以了。对于每一个节点，他们的子树的权值都可以建成一颗01trie。
写的时候别忘了将树给free掉，不然内存很大，用递归套递归去写会爆系统栈。。。
#include <bits/stdc++.h> #define MAXN 200005 #define ll long long using namespace std; struct Tree { Tree *next[2]; }; struct node { int id, ret, u; }; int val[MAXN]; vector<int> e[MAXN]; vector<node> qs[MAXN]; int lans[MAXN]; Tree *root[MAXN]; void insert(int ret, Tree *rt) { Tree *q = rt; for (int i = 29; i >= 0; i--) { int p = 0; if (ret & (1 << i)) { p = 1; } if (q -> next[p] == NULL) { Tree *tmp = new Tree; tmp -> next[0] = tmp -> next[1] = NULL; q -> next[p] = tmp; } q = q -> next[p]; } } int query(int ret, Tree *rt) { Tree *q = rt; int ans = 0; for (int i = 29; i >= 0; i--) { int p = 0; if (ret & (1 << i)) { p = 1; } if (q -> next[p ^ 1] != NULL) { ans |= (1 << i); q = q -> next[p ^ 1]; } else { q = q -> next[p]; } } return ans; } void delTree(Tree *rt) { if (rt -> next[0] != NULL) { delTree(rt -> next[0]); } if (rt -> next[1] != NULL) { delTree(rt -> next[1]); } free(rt); } Tree *merge(Tree *r1, Tree *r2) { if (r1 == NULL) { return r2; } if (r2 == NULL) { return r1; } r1 -> next[0] = merge(r1 -> next[0], r2 -> next[0]); r1 -> next[1] = merge(r1 -> next[1], r2 -> next[1]); free(r2); return r1; } void addEdge(int u, int v) { e[u].push_back(v); e[v].push_back(u); } void init() { for (int i = 0; i < MAXN; i++) { e[i].clear(); qs[i].clear(); } } void dfs(int u, int fa) { root[u] = new Tree; root[u] -> next[0] = root[u] -> next[1] = NULL; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) { continue; } dfs(v, u); merge(root[u], root[v]); } insert(val[u], root[u]); for (int i = 0; i < qs[u].size(); i++) { lans[qs[u][i].id] = query(qs[u][i].ret, root[u]); } } int main() { int n, q, tmp; node tmpp; while (~scanf("%d %d", &n, &q)) { init(); for (int i = 1; i <= n; i++) { scanf("%d", &val[i]); } for (int i = 2; i <= n; i++) { scanf("%d", &tmp); addEdge(i, tmp); } for (int i = 1; i <= q; i++) { scanf("%d %d", &tmpp.u, &tmpp.ret); tmpp.id = i; qs[tmpp.u].push_back(tmpp); } dfs(1, -1); for (int i = 1; i <= q; i++) { printf("%d\n", lans[i]); } delTree(root[1]); } } /* 2 2 1 2 1 1 3 2 1 */两天后发现。。当时free错东西，hdu给我报了个stack_overflow的re。明明就是re嘛。。。 留回我指针写的鬼畜代码。
#pragma comment(linker, "/STACK:102400000,102400000") #include <bits/stdc++.h> #define MAXN 200005 #define ll long long using namespace std; struct Tree { Tree *lson, *rson; }; struct node { int id, ret, u; }; int ans; int val[MAXN]; vector<int> e[MAXN]; vector<node> qs[MAXN]; int lans[MAXN]; Tree *insert(int idx, int ret, Tree *root) { if (idx == -1) { Tree *rt = (Tree *)malloc(sizeof(Tree)); rt -> lson = NULL; rt -> rson = NULL; return rt; } if (root == NULL) { root = (Tree *)malloc(sizeof(Tree)); root -> lson = NULL; root -> rson = NULL; } int p = ret & (1 << idx); if (p) { root -> lson = insert(idx - 1, ret, root -> lson); } else { root -> rson = insert(idx - 1, ret, root -> rson); } return root; } void query(int idx, int ret, Tree *root) { if (idx == -1) { return ; } int p = ret & (1 << idx); if (p) { if (root -> rson != NULL) { query(idx - 1, ret, root -> rson); } else if (root -> lson != NULL) { ans ^= (1 << idx); query(idx - 1, ret, root -> lson); } } else { if (root -> lson != NULL) { ans ^= (1 << idx); query(idx - 1, ret, root -> lson); } else if (root -> rson != NULL) { query(idx - 1, ret, root -> rson); } } } void delTree(Tree *root) { if (root -> lson != NULL) { delTree(root -> lson); } if (root -> rson != NULL) { delTree(root -> rson); } free(root); } Tree *merge(Tree *r1, Tree *r2) { if (r1 == NULL) { return r2; } if (r2 == NULL) { return r1; } r1 -> lson = merge(r1 -> lson, r2 -> lson); r1 -> rson = merge(r1 -> rson, r2 -> rson); free(r2); return r1; } void addEdge(int u, int v) { e[u].push_back(v); e[v].push_back(u); } void init() { for (int i = 0; i < MAXN; i++) { e[i].clear(); qs[i].clear(); } } Tree *dfs(int u, int fa) { Tree *root = (Tree *)malloc(sizeof(Tree)); root -> lson = NULL; root -> rson = NULL; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) { continue; } merge(root, dfs(v, u)); } insert(30, val[u], root); for (int i = 0; i < qs[u].size(); i++) { ans = qs[u][i].ret; query(30, ans, root); lans[qs[u][i].id] = ans; } return root; } int main() { int n, q, tmp; node tmpp; while (~scanf("%d %d", &n, &q)) { init(); for (int i = 1; i <= n; i++) { scanf("%d", &val[i]); } for (int i = 2; i <= n; i++) { scanf("%d", &tmp); addEdge(i, tmp); } for (int i = 1; i <= q; i++) { scanf("%d %d", &tmpp.u, &tmpp.ret); tmpp.id = i; qs[tmpp.u].push_back(tmpp); } delTree(dfs(1, -1)); for (int i = 1; i <= q; i++) { printf("%d\n", lans[i]); } } } /* 2 2 1 2 1 1 3 2 1 */