P3781 [SDOI2017] Cut Tree Game

Hack testdata by boshi & Remmina.

Xiao Q is someone who loves to learn. He often goes to Wikipedia to study computer science. Just now, Xiao Q carefully studied a series of bitwise operators, among which the bitwise XOR operator $\oplus$ impressed him a lot. The bitwise XOR operator is a binary operator. Bitwise XOR is commutative, i.e., $i \oplus j = j \oplus i$. He found that bitwise XOR can be understood as: for the binary representations of the numbers being operated on, if the corresponding bits are the same, then the result’s bit is $0$, otherwise it is $1$, for example: $1(01) \oplus 2(10) = 3(11)$. He also found that bitwise XOR can be understood as performing addition without carry on each binary bit of the numbers involved, for example: $3(11) \oplus 3(11) = 0(00)$. Now Xiao Q has an unrooted tree $T$ with $n$ nodes, numbered from $1$ to $n$, where the weight of node $i$ is $v_i$. Define the value of a tree as the XOR of the weights of all its nodes. A connected subtree of a tree $T$ is a connected subgraph of $T$ that is also a tree. Xiao Q wants to play a cut-tree game on this tree. He will repeatedly perform the following two operations: - Change x y: change the weight of node $x$ to $y$. - Query k: ask how many nonempty connected subtrees of $T$ have value exactly $k$. Xiao Q really likes (but is not good at) math, and he hopes you can answer his questions quickly. Can you write a program to help him?

- The first line contains two positive integers $n$, $m$, representing the number of nodes and the upper bound of weights. - The second line contains $n$ nonnegative integers $v_1, v_2, \dots, v_n$, representing the initial weight of each node. - The next $n - 1$ lines each contain two positive integers $a_i$, $b_i$, indicating that there is an undirected tree edge connecting $a_i$ and $b_i$. - The next line contains a positive integer $q$, representing the number of operations Xiao Q performs. - The next $q$ lines each describe one operation in order.

Output several lines, each containing one integer, answering each query in order. Since the answer may be large, output it modulo $10007$.

Constraints: For $100\%$ of the testdata, $1 \leq a_i, b_i, x \leq n$, $0 \leq v_i, y, k < m$, and the number of Change operations does not exceed $10000$.  Translated by ChatGPT 5