Weasel does Xor on Tree

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
A tree is an undirected graph in which each pair of vertices is connected to each other by exactly one path. Weasel has a tree with N nodes. The indexing of the nodes is 0based and the tree is rooted at node 0. Every node i has an initial value X_{0i}.
Every day d > 0, he performs the following operations, starting from the root:
 Weasel computes X_{du} as the bitwisexor sum of all the values X_{d − 1v} for a node v in u's subtree.
 He recursively proceeds to perform the operation for every child of u.
For Q values of Δ, Weasel wants to compute X_{Δ0}.
Input
The first line of the input contains two integers N and Q.
Each of the following N − 1 lines contains two integers, u and v, an edge in the tree.
On the following line there are N integers, representing the X_{0} array.
Each of the next Q lines contains values for Δ as noted in the statement.
Output
You should print Q lines, each containing X_{Δ0}.
Constraints
 1 ≤ N, Q ≤ 2 * 10^{5}
 0 ≤ X_{0i} ≤ 10^{18} for every 0 ≤ i ≤ N − 1.
 0 ≤ Δ ≤ 10^{18}
 0 ≤ u, v ≤ N − 1
Subtasks
 Subtask 1 (20 points): 1 ≤ N ≤ 500 and Δ ≤ 500
 Subtask 2 (20 points): 1 ≤ N ≤ 1000 and 1 ≤ N × Q ≤ 10^{6}
 Subtask 3 (10 points): 1 ≤ N ≤ 5000
 Subtask 4 (50 points): original constraints
Example
Input: 4 3 0 1 1 2 0 3 1 5 8 7 1 2 3 Output: 11 9 3
Explanation
Initially X_{0} = [1, 5, 8, 7].
Weasel performs his operation on node 0: X_{10} = X_{00} xor X_{01} xor X_{02} xor X_{03} = 1 xor 5 xor 8 xor 7 = 11.
X_{11} = X_{01} xor X_{02} = 5 xor 8 = 13.
X_{12} and X_{13} remain equal to X_{02}, respectively X_{03}.
Author:  bciobanu 
Tester:  jingbo_adm 
Editorial  https://discuss.codechef.com/problems/WEASELTX 
Tags  bciobanu, binomial, lucastheorem, mediumhard, sept17 
Date Added:  9082017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions