hdu-6191 给定一棵树以及每个节点的权值，给定多组询问，每次询问在u子树中与x异或值最大是多少 离线+字典树 先离线把问题都放到节点中，然后dfs每个节点赋予dfs序，同时生成字典树，并记录当前节点最大的dfs序是多少，当回溯时，只要字典树的节点是大于等于当前节点的dfs序，那么都是这个节点的子树，对于每一个询问找到最大值即可
#include <bits/stdc++.h> #include <vector> using namespace std; const int maxn = 100010; struct Node { int l, r, t; Node() {l = r = t = 0;} Node(int ll, int rr, int tt): l(ll), r(rr), t(tt) {} }; vector<Node> F, Q[maxn]; vector<int> G[maxn]; int a[maxn], num[maxn], n, m, t, b[40], ans[maxn], x, y; void init() { F.clear(); for (int i = 1; i <= n; i++) G[i].clear(); for (int i = 1; i <= n; i++) Q[i].clear(); F.push_back(Node(0, 0, 0)); } void insert(int x, int t) { memset(b, 0, sizeof(b)); while (x) { b[++b[0]] = x%2; x /= 2; } int p = 0; F[p].t = t; for (int i = 30; i >= 1; i--) { if (b[i]) { if (!F[p].r) { F.push_back(Node(0, 0, t)); F[p].r = F.size()-1; } p = F[p].r; F[p].t = t; } else { if (!F[p].l) { F.push_back(Node(0, 0, t)); F[p].l = F.size()-1; } p = F[p].l; F[p].t = t; } } } int get(int c, int t) { memset(b, 0, sizeof(b)); while (c) { b[++b[0]] = c%2; c /= 2; } int p = 0, k = 0, o = 1; for (int i = 1; i < 30; i++) o = o*2; for (int i = 30; i >= 1; i--) { if (b[i]) { if (F[p].l && F[F[p].l].t >= t) { p = F[p].l; k += o; } else { p = F[p].r; } } else { if (F[p].r && F[F[p].r].t >= t) { p = F[p].r; k += o; } else { p = F[p].l; } } o = o/2; } return k; } void dfs(int x) { t++; num[x] = t; insert(a[x], t); for (int i = 0; i < G[x].size(); i++) { dfs(G[x][i]); } for (int i = 0; i < Q[x].size(); i++) { int c = Q[x][i].l, id = Q[x][i].r; ans[id] = get(c, num[x]); } } int main() { while (scanf("%d %d", &n, &m) != EOF) { init(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 2; i <= n; i++) { scanf("%d", &x); G[x].push_back(i); } for (int i = 1; i <= m; i++) { scanf("%d %d", &x, &y); //x node | y int Q[x].push_back(Node(y, i, 0)); } dfs(1); for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); } }