Query on A Tree

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 0    Accepted Submission(s): 0 Problem Description 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.   Sample Input 2 2 1 2 1 1 3 2 1   Sample Output 2 3   Statistic |  Submit |  Clarifications |  Back 题意：给你一棵树，每个点都有权值，q次询问，每次询问给你u和x，问以u为根的子树与x的异或值最大为多少。

思路：现场思路已经想通了，但是码了两个小时没码出来。。。好尴尬。官方题解思路好像是从底层出发启发式合并，我这里给个不一样的思路，按照dfs序建可持久化字典树，以u为根的子树的字典树=以u为根的子树的最后一个节点的字典树-u按照dfs的前一个节点的字典树。然后就可以在线查询了。下面给代码：

#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cmath> #include<queue> #include<cstdio> #include<queue> #include<algorithm> #include<cstring> #include<string> #include<utility> #include<set> #include<map> #include<stack> #include<vector> #define maxn 100005 #define inf 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long LL; const double eps = 1e-5; const int mod = 1e9+7; int root[maxn], ls[maxn * 33], rs[maxn * 33], val[maxn * 33], index, ans, len, head[maxn], pre[maxn], last[maxn], temp, a[maxn]; struct node{ int v, next; }p[maxn]; int newnode(int key){ val[index] = key; return index++; } int insert(int step, int now1,int key){ bool jud = (now1 == -1); int now2 = newnode(jud ? 1 : val[now1] + 1); if (!step) return now2; if ((1 << (step - 1))&key){ ls[now2] = jud ? -1 : ls[now1]; rs[now2] = insert(step - 1, jud ? -1 : rs[now1], key); } else{ rs[now2] = jud ? -1 : rs[now1]; ls[now2] = insert(step - 1, jud ? -1 : ls[now1], key); } return now2; } bool query(int step, int now1, int now2, int x,bool flag){ if (step == -1) return true; if (now2 == -1 || (now1 >= 0 && !(val[now2] - val[now1]))) return false; if (flag) ans ^= 1 << step; bool jud = (now1 == -1); if ((1 << (step - 1))&x){ if (query(step - 1, jud ? -1 : ls[now1], ls[now2], x, 0)) return true; query(step - 1, jud ? -1 : rs[now1], rs[now2], x, 1); } else{ if (query(step - 1, jud ? -1 : rs[now1], rs[now2], x, 1)) return true; query(step - 1, jud ? -1 : ls[now1], ls[now2], x, 0); } return true; } void addedge(int u, int v){ p[len].v = v; p[len].next = head[u]; head[u] = len++; } void dfs(int x, int fa){ last[x] = x; pre[x] = temp; root[x] = insert(31, root[temp], a[x]); temp = x; for (int i = head[x]; ~i; i = p[i].next){ if (p[i].v == fa) continue; dfs(p[i].v, x); last[x] = last[p[i].v]; } } int main(){ root[0] = -1; int n, q; while (~scanf("%d%d", &n, &q)){ memset(head, -1, sizeof(head)); len = index = temp = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 2; i <= n; i++){ int x; scanf("%d", &x); addedge(x, i); } dfs(1, 0); while (q--){ int u, x; scanf("%d%d", &u, &x); ans = x; query(31, root[pre[u]], root[last[u]], x, 0); printf("%d\n", ans); } } }