P15044 [UOI 2022 II Stage] Tree

Xsonia has a rooted tree with root vertex $1$ and $n$ vertices. Each vertex has a number written on it. The number written on vertex $i$ is $a_i$. Recall that a tree is a connected graph with no cycles. A rooted tree means choosing one vertex in the tree as the root. In a rooted tree, the ancestors of a vertex $v$ are all vertices on the path from $v$ to the root (excluding $v$ itself). The subtree of a vertex $v$ is the set of all vertices that have $v$ as an ancestor, including $v$ itself. The XOR sum of a set $S = (u_1, u_2, u_3, \dots, u_k)$ is defined as $u_1 \oplus u_2 \oplus u_3 \oplus \dots \oplus u_k$, where $\oplus$ is the bitwise XOR operation, written as `xor` in Pascal, and as `^` in C++/Java/Python. For a set of numbers $S$, consider the set of XOR sums of all its possible subsets. Call this set $F(S)$. Xsonia’s friends keep asking her questions like this: “If we consider the multiset of all numbers in the subtree of vertex $v$ (denoted as $U_v$), what is the $k$-th smallest number in the set $F(U_v)$?” In other words, if we take all numbers in the subtree of vertex $v$ and consider the XOR sums of all their subsets, what is the $k$-th smallest number in the resulting set? If such a number does not exist (i.e., $k > |F(U_v)|$), then Xsonia answers $-1$. Note that $F(U_v)$ is a set, not a multiset. That is, even if a number appears multiple times, it is counted only once. In addition, Xsonia’s friends sometimes ask her to modify a number on the tree.

The first line contains two integers $n, g$ ($2 \leq n \leq 5 \cdot 10^4$, $0 \leq g \leq 7$), representing the number of vertices in the tree and the test group ID, respectively. The next $n - 1$ lines each contain two integers $x_i, y_i$ ($1 \leq x_i, y_i \leq n$), indicating that there is an edge between vertices $x_i$ and $y_i$. It is guaranteed that the graph is a tree. The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i < 2^{20}$), representing the initial array $a$ of numbers on the vertices. The next line contains an integer $q$ ($1 \leq q \leq 5 \cdot 10^4$), representing the number of queries. Each of the next $q$ lines describes one query. A query that modifies a number has the format $1 \ x_i \ y_i$ ($1 \leq x_i \leq n$, $0 \leq y_i < 2^{20}$). This means the number on vertex $x_i$ becomes $y_i$. The other type of query has the format $2 \ v_i \ k_i$ ($1 \leq v_i \leq n$, $1 \leq k_i \leq 10^9$). This query asks for 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 XOR sums of all its subsets. If $k_i > |F(U_{v_i})|$, output $-1$.

For each query of the second type, output the answer on a separate line.

### Sample Explanation Explanation for the first sample. The number next to each vertex is $a_i$. :::align{center}  ::: In the first query, consider the subtree of vertex $2$. It contains the numbers $1, 2, 3$. $F([1,2,3]) = [0, 1, 2, 3]$. In the second query, consider the whole subtree. $F([1, 2, 3, 4]) = [0,1,2,3,4,5,6,7]$. After modifying one number, the tree becomes: :::align{center}  ::: Now, the subtree of vertex $2$ contains the numbers $1, 2, 4$. $F([1,2,4]) = [0,1,2,3,4,5,6,7]$. ### Scoring - (6 points): $q, n \leq 15$. - (16 points): $q, n \leq 500$. - (18 points): $q, n \leq 2000$. - (7 points): In all second-type queries, $v_i = 1$. - (13 points): There are no modification queries. - (11 points): All $a_i, y_i$ are powers of $2$. - (29 points): No additional constraints. Translated by DeepSeek V3. Translated by ChatGPT 5