Monkey A lives on a tree, he always plays on this tree. One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once. Monkey A gave a value to each node on the tree. And he was curious about a problem. The problem is how large the xor result of number x and one node value of label y can be, when giving you a non-negative integer x and a node label u indicates that node y is in the subtree whose root is u(y can be equal to u). Can you help him?
Input
There are no more than 6 test cases. For each test case there are two positive integers n and q, indicate that the tree has n nodes and you need to answer q queries. Then two lines follow. The first line contains n non-negative integers V1,V2,⋯,Vn, indicating the value of node i. The second line contains n-1 non-negative integers F1,F2,⋯Fn−1, Fi means the father of node i+1. And then q lines follow. In the i-th line, there are two integers u and x, indicating that the node you pick should be in the subtree of u, and x has been described in the problem. 2≤n,q≤105 0≤Vi≤109 1≤Fi≤n, the root of the tree is node 1. 1≤u≤n,0≤x≤109
Output
For each query, just print an integer in a line indicating the largest result.
思路：让你在根节点为u的子树里找一个结点，使得其与给定x的异或值最大。
用dfs序来建立01字典树，然后就可以在区间里进行查找了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; int a[maxn]; //结点值 int L[maxn], R[maxn]; //DFS序 int num[maxn * 40]; //结点出现次数 int Root[maxn * 40]; //树根节点 ll val[maxn * 40]; //字典树的值 int tree[maxn * 40][2]; //字典树 vector<int> e[maxn]; int lcnt, tcnt;// 结点数，树的数量 void init(int n) { for(int i = 0; i <= n; ++i) e[i].clear(); memset(num, 0, sizeof(num)); memset(Root, 0, sizeof(Root)); memset(val, 0, sizeof(val)); tree[0][1] = tree[0][0] = 0; Root[0] = 0, num[0] = 0; lcnt = tcnt = 0; } void ins(ll x) { int u = tcnt, pre = Root[lcnt - 1]; for(int i = 32; i >= 0; --i) { int w = (x >> i) & 1; //复制上一棵树 tree[u][0] = tree[pre][0]; tree[u][1] = tree[pre][1]; tree[u][w] = ++tcnt; //更新 num[tcnt] = num[tree[pre][w]] + 1; //相当于做前缀和 u = tree[u][w]; pre = tree[pre][w]; } val[u] = x; //保存值 } ll query(int l, int r, ll x) { for(int i = 32; i >= 0; --i) { int w = (x >> i) & 1; //贪心找不一样的，并且这个区间不为空 if(tree[r][w ^ 1] && num[tree[r][w ^ 1]] - num[tree[l][w ^ 1]]) { l = tree[l][w ^ 1]; r = tree[r][w ^ 1]; } else { l = tree[l][w]; r = tree[r][w]; } } return val[r]; } void dfs(int x) //dfs序 { L[x] = ++lcnt, Root[lcnt] = ++tcnt; //记录左区间和根节点 ins(a[x]); //插入 for(int v = 0; v < e[x].size(); ++v) dfs(e[x][v]); R[x] = lcnt; //记录右区间 } int main() { int n, q; while(~scanf("%d%d", &n, &q)) { init(n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); int u; for(int i = 1; i < n; ++i) { scanf("%d", &u); e[u].push_back(i + 1); } dfs(1); while(q--) { ll u, x; scanf("%lld%lld", &u, &x); ll ans = query(Root[L[u]-1], Root[R[u]], x); //在这个子树里寻找 printf("%lld\n", x ^ ans); } } return 0; }
