P5127 Subset XOR Sum.

Xiao L and Xiao K are having a heated discussion. (You do not need to know who said which line...) “Do you know non-empty subsets?” “Of course! For example, for the set $\{1,2,3\}$, all of its non-empty subsets are $\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}$.” “Then do you know the XOR sum of the numbers in each non-empty subset?” “I do! It is just $1,2,3,1⊕2=3,2⊕3=1,1⊕3=2,1⊕2⊕3=0$.” “Then do you know what their total sum is? We call it the subset XOR sum.” “Subset XOR sum... what a strange name, but I know it is $1+2+3+3+1+2+0=12$.” “Then let me ask you, what is the subset XOR sum of $\{a_1,a_2,...,a_n\}$?” “Just brute force it slowly!” “What if $n\le 200000$?” “...” “What if we put the problem on a tree?” “... Can you solve it then?” “Of course... I cannot...” Now only you can help Xiao L and Xiao K. Please solve this problem. **To express the statement more clearly, we explain it again.** There is a tree with $n$ nodes, and there are $m$ operations in total. These operations are given in order. Each operation is either a query or a modification. Each query operation gives two node indices $a,b$. As is well known, there is a unique path between $a$ and $b$ on the tree. Let the multiset of node weights of all nodes on this path be $S$. You need to output the subset XOR sum of $S$. The answer is taken $mod\space(10^9+7)$. Each modification operation gives two node indices $a,b$ and an integer value $c$. You need to XOR the weight of every node on the unique path from node $a$ to node $b$ by $c$. **Here, “set” means multiset.**

The first line contains three positive integers $n,m$. The next $n-1$ lines each contain two positive integers $a,b$, meaning there is an edge between node $a$ and node $b$. There will be no multiple edges or self-loops. The next line contains $n$ non-negative integers. The $i$-th non-negative integer is the initial weight of node $i$. The next $m$ lines each contain several integers describing an operation. The first integer of each line is either $1$ or $2$. If it is $1$, then this operation is a query, and the next two numbers are $a,b$; if it is $2$, then this operation is a modification, and the next three numbers are $a,b,c$.

For each query, output one line containing the answer.

Sample explanation: For the first query, the path from $1$ to $1$ passes through node $1$, the multiset of node weights is $\{1\}$, and the subset XOR sum is $1$. After two modifications, the weight of node $1$ is $0$, and the weight of node $3$ is $1$. For the second query, the multiset of node weights on the path from $1$ to $3$ is $\{0,1\}$, and the subset XOR sum is $0+1+1=2$. This problem has $10$ test points. Each test point is worth $10$ points, for a total of $100$ points. | Test point ID | Range of $n$ | Range of $m$ | Special property | | :----------: | :----------: | :----------: | :----------: | | $1-2$ | $1\le n\le 1000$ | $1\le m\le 1000$ | None | | $3-5$ | $1\le n\le 200000$ | $1\le m\le 200000$ | The indices of the two nodes connected by each edge are adjacent | | $6-10$ | $1\le n\le 200000$ | $1\le m\le 200000$ | None | Constraints: For $100\%$ of the data, all input numbers are non-negative integers not greater than $10^9+7$, and $1\le a,b\le n$. Translated by ChatGPT 5