P6053 [RC-02] XOR

FangZeLi likes XOR, so this problem was created (though that is not really why he makes such problems).

**Note: In this problem, every $\sum$ means taking the XOR-sum.** There is a rooted tree with $n$ nodes and $n-1$ edges. Initially, node $1$ is the root. Each node $i$ on the tree has a node value $V_{i}$. Define the function $\operatorname{Xor}(x)=\sum_{y\in \operatorname{Subtree}(x)}{V_{y}}$, where $\operatorname{Subtree}(x)$ denotes the subtree of $x$. You need to support the following five operations: 1. `1 x`: Make $x$ the root, and query $\sum_{i=1}^{n}{\operatorname{Xor}(i)}$. 2. `2 x y`: Set $V_{x}=y$. 3. `3 x y`: Query $\operatorname{LCA}(x,y)$. 4. `4 x y`: Query the XOR-sum of node values along the path from $x$ to $y$. 5. `5 x`: Query $\operatorname{Xor}(x)$.

The first line contains three integers $n,m,q$, representing the number of nodes, the number of operation type $1$, and the number of the remaining operations. The next line contains $n$ integers, representing $V_{1}\dots V_{n}$. The next $n-1$ lines each contain two integers $x,y$, indicating that there is an edge between $x$ and $y$. The next $m+q$ lines each contain two or three integers. The first number is the operation type, followed by the parameters of that operation.

Output several lines, each being the result of operations $1,3,4,5$.

For all testdata, it is guaranteed that $100\le n,m,q\le 10^6$, $0\le V_i\le 2^{31}-1$. The detailed Constraints are shown in the table below. | Test Point ID | Time Limit / s | $n$ | $m$ | $q$ | | :-----: | :--------: | :------------------: | :------------------: | :-------------------: | | $1$ | $1$ | $ 100 $ | $ 100 $ | $ 4 \times 10 ^ 5 $ | | $2,3$ | $1$ | $ 100 $ | $10^ { 6 }$ | $ 4 \times 10 ^ 5 $ | | $4,5$ | $1$ | $ 10 ^ 4$ | $100$ | $ 4 \times 10 ^ 5 $ | | $6,7,8$ | $ 1 $ | $ 10 ^ 4$ | $10 ^ 6$ | $ 4 \times 10 ^ 5 $ | | $9$ | $ 1.8 $ | $ 10 ^ 6$ | $100$ | $ 10^6$ | | $10$ | $ 2.3 $ | $ 10 ^ 6$ | $ 10^6$ | $ 10 ^ 6$ | Translated by ChatGPT 5