LB出题
Time Limit : 9000/3000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 12 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
在LB学了不少算法之后，他决定自己也出一个题来给小学弟做。给定一棵n个节点的以1为根的树，节点i上有权值w[i]，节点i的深度为deep[i]。有多个询问每次询问给定一组x,k令x1 = (x^last_ans)%n+1,k1 = k%deep[x]+1，那么在x1到根的路径上任选一个节点y有z = w[x] xor w[y]（xor为异或运算），在所有z的值中求第k1小。deep[1]=1，last_ans表示上一次询问的答案，初始时last_ans=0。
Input
多组数据，每组数据第一行输入n,q，第二行n个整数表示1~n这n个节点的点权。接下来的n-1行表示树中的边a,b表示节点a与节点b相连。最后q行表示q个询问每组询问输入x,k。
Output
每组数据输出q行表示每次询问取得的第k小的异或值。
Sample Input
5 5 3 7 9 5 2 1 2 1 3 3 4 4 5 2 1 2 2 4 1 4 2 4 3
Sample Output
10 12 6 0 11