Xonya and the Tree#11071
Xonya has a rooted tree with vertices, rooted at vertex , where each vertex has a number written on it. The -th vertex has the number a_i written on it.
Recall that a tree is a connected graph without cycles. A rooted tree is a tree in which one vertex is chosen as the root.
An ancestor of vertex in a rooted tree is any vertex that lies on the path from to the root, excluding vertex itself. The subtree of vertex is the set of all vertices for which is an ancestor, including vertex itself.
The XOR sum of a set S = (u_1, u_2, u_3, \dots, u_k) is defined as the number u_1 \oplus u_2 \oplus u_3 \oplus \dots \oplus u_k, where is the bitwise exclusive disjunction operation, denoted as «xor» in Pascal and «^» in C++/Java/Python.
For a set of numbers , consider the set of XOR sums of all possible subsets of . Let's call this set .
Xonya's friend constantly asks her questions — "If we consider the set of all numbers written in the subtree of vertex (let's call it U_v), what number in the set F(U_v) will be the -th smallest?". In other words, if we take all numbers from the subtree of vertex and consider all XOR sums of their subsets, what number in the resulting set will be at the -th position in ascending order? If such a number does not exist (k > |F(U_v)|), then Xonya answers with . Note that F(U_v) is a set, not a multiset. That is, if a number appears multiple times, it should be counted only once.
Also, sometimes Xonya's friend asks her to change one of the numbers in the tree.
The first line contains two integers (2 \leq n \leq 5 \cdot 10^4, 0 \leq g \leq 7) — the number of vertices in the tree and the group number.
Each of the next n - 1 lines contains two integers x_i, y_i (1 \leq x_i, y_i \leq n). This means that there is an edge between vertices x_i and y_i in the tree. It is guaranteed that the graph is a tree.
The next line contains integers a_1, a_2, \dots, a_n (0 \leq a_i < 2^{20}) — the array of initial numbers on the tree vertices.
The next line contains one integer (1 \leq q \leq 5 \cdot 10^4) — the number of queries.
Each of the next lines describes one query.
Queries to change a number in the tree have the form 1 \ x_i \ y_i (1 \leq x_i \leq n, 0 \leq y_i < 2^{20}). Such a query means that the number y_i is now written on the x_i-th vertex.
Queries of the other type have the form 2 \ v_i \ k_i (1 \leq v_i \leq n, 1 \leq k_i \leq 10^9). Such a query means that you need to find the k_i-th smallest number in the set F(U_{v_i}), where U_{v_i} is the set of numbers in the subtree of vertex v_i, and F(U_{v_i}) is the set of all possible XOR sums of its subsets. If k_i > |F(U_{v_i})|, output .
For each query of the second type, output the answer on a separate line.
Example 1
Explanation of the first example. The numbers next to the vertices are a_i.
In the first query, the subtree of vertex is considered. It contains the numbers .
F([1,2,3]) = [0, 1, 2, 3].
In the second query, the entire subtree is considered. F([1, 2, 3, 4]) = [0,1,2,3,4,5,6,7].
After changing one number, the tree looks like this.
Now in the subtree of vertex the numbers are .
F([1,2,4]) = [0,1,2,3,4,5,6,7].
( points): q, n \leq 15.
( points): q, n \leq 500.
( points): q, n \leq 2000.
( points): In all queries of the second type v_i = 1.
( points): There are no queries to change a number.
( points): All a_i, y_i are powers of 2.
( points): No additional constraints.