题意：给你一棵树，每个节点一个权值，然后m次查询，每次查询以u为根节点的子树上的某点与x异或的最大值。
题解：比赛时死活不会写，当时没学可持久化字典树，暴力写了一发，然后无限TLE。。。其实就是一道可持久化字典树模板题，我们可以将树上的权值转化为区间问题，呢就用DFS序好了，剩下的跑一发可持久化字典树就OK了。
#include<set> #include<map> #include<stack> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> #include<functional> using namespace std; typedef long long ll; #define inf 1000000000 #define mod 1000000007 #define maxn 260005 #define PI acos(-1.0) #define lowbit(x) (x&-x) #define eps 1e-9 vector<int>q[maxn]; int n, m, t, a[maxn], id[maxn], rt[maxn], st[maxn], ed[maxn], b[maxn]; struct node { int cnt; int ch[maxn * 32][2], sum[maxn * 32]; void init() { cnt = 0;b[0] = 1; for (int i = 1;i <= 30;i++) b[i] = b[i - 1] * 2; memset(ch, 0, sizeof(ch)); memset(sum, 0, sizeof(sum)); } int insert(int x, int val) { int res, y; y = res = ++cnt; for (int i = 30;i >= 0;i--) { ch[y][0] = ch[x][0]; ch[y][1] = ch[x][1]; sum[y] = sum[x] + 1; int tmp = val&b[i]; tmp >>= i;x = ch[x][tmp]; ch[y][tmp] = ++cnt;y = ch[y][tmp]; } sum[y] = sum[x] + 1; return res; } int query(int l, int r, int val) { int ans = 0; for (int i = 30;i >= 0;i--) { int tmp = val&b[i]; tmp >>= i; if (sum[ch[r][tmp ^ 1]] - sum[ch[l][tmp ^ 1]]) ans += b[i], l = ch[l][tmp ^ 1], r = ch[r][tmp ^ 1]; else l = ch[l][tmp], r = ch[r][tmp]; } return ans; } }trie; void dfs(int u, int p) { st[u] = ++t; id[t] = u; for (int i = 0;i < q[u].size();i++) { int v = q[u][i]; if (v == p) continue; dfs(v, u); } ed[u] = t; } int main(void) { int i, j, x; while (scanf("%d%d", &n, &m) != EOF) { t = 0;rt[0] = 0; trie.init(); for (i = 1;i <= n;i++) scanf("%d", &a[i]), q[i].clear(); for (i = 2;i <= n;i++) { scanf("%d", &x); q[x].push_back(i); } dfs(1, 0); for (i = 1;i <= n;i++) rt[i] = trie.insert(rt[i - 1], a[id[i]]); int l, r, root, x; while (m--) { scanf("%d%d", &root, &x); l = st[root];r = ed[root]; printf("%d\n", trie.query(rt[l - 1], rt[r], x)); } } return 0; }
