题意
给你一棵带点权的树，每次查询 \(u\) 和 \(x\) ，求以 \(u\) 为根结点的子树上的结点与 \(x\) 异或后最大的结果。
分析
看到子树，直接上树上启发式合并，看到异或，上 \(Trie\) 。
这道题就是两个经典的题目结合了一波。树上启发式合并处理这种需要查询整个子树的题目尤其有用，可以复用大量的信息。
离线查询后，到要查询的结点直接在 \(Trie\) \(01\) 树上跑一下即可。先去理解一波 树上启发式合并（\(dsu \ on \ tree\)），就会发现这真是一道模板题。
code
#includeusing namespace std;typedef long long ll;const int MAXN = 1e5 + 100;const int MX = 30;struct Ex { int id, x;};struct Trie { int val[MAXN * 30], nxt[MAXN * 30][2], L, root; int newnode() { memset(nxt[L], -1, sizeof nxt[L]); return L++; } void init() { L = 0; root = newnode(); } void update(int x, int key) { int now = root; for(int i = MX; i >= 0; i--) { int o = (x >> i) & 1; if(nxt[now][o] == -1) nxt[now][o] = newnode(); now = nxt[now][o]; val[now] += key; } } int query(int x) { int res = 0; int now = root; for(int i = MX; i >= 0; i--) { int o = (x >> i) & 1; if(val[nxt[now][!o]]) { now = nxt[now][!o]; res |= (1 << i); } else { now = nxt[now][o]; } } return res; }}trie;vector ex[MAXN];int fa[MAXN], son[MAXN], dep[MAXN], siz[MAXN];int col[MAXN];int cnt, head[MAXN];struct Edge { int to, next;}e[MAXN << 1];void addedge(int u, int v) { e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt++;}void dfs(int u) { siz[u] = 1; son[u] = 0; for(int i = head[u]; ~i; i = e[i].next) { if(e[i].to != fa[u]) { fa[e[i].to] = u; dep[e[i].to] = dep[u] + 1; dfs(e[i].to); if(siz[e[i].to] > siz[son[u]]) son[u] = e[i].to; siz[u] += siz[e[i].to]; } }}int n, q;int vis[MAXN];int ans[MAXN];void update(int u, int key) { trie.update(col[u], key); for(int i = head[u]; ~i; i = e[i].next) { if(e[i].to != fa[u] && !vis[e[i].to]) update(e[i].to, key); }}void dfs1(int u, int flg) { for(int i = head[u]; ~i; i = e[i].next) { if(e[i].to != fa[u] && e[i].to != son[u]) dfs1(e[i].to, 1); } if(son[u]) { dfs1(son[u], 0); vis[son[u]] = 1; } update(u, 1); for(int i = 0; i < ex[u].size(); i++) { ans[ex[u][i].id] = trie.query(ex[u][i].x); } if(son[u]) vis[son[u]] = 0; if(flg) { update(u, -1); }}int main() { while(~scanf("%d%d", &n, &q)) { for(int i = 1; i <= n; i++) { ex[i].clear(); fa[i] = son[i] = dep[i] = siz[i] = 0; } memset(vis, 0, sizeof vis); memset(ans, 0, sizeof ans); trie.init(); cnt = 0; memset(head, -1, sizeof head); for(int i = 1; i <= n; i++) { scanf("%d", &col[i]); } for(int i = 2; i <= n; i++) { int u; scanf("%d", &u); addedge(u, i); addedge(i, u); } for(int i = 0; i < q; i++) { int u, x; scanf("%d%d", &u, &x); ex[u].push_back(Ex{i, x}); } dfs(1); dfs1(1, -1); for(int i = 0; i < q; i++) { printf("%d\n", ans[i]); } } return 0;}