P6053 [RC-02] XOR

FangZeLi 喜欢异或，所以就有了这道题（然而这并不是他出这种题的理由）。

**注意，本题中一切 $\sum$ 均表示求异或和！** 一棵 $n$ 个节点，$n-1$ 条边的有根树，初始时以 $1$ 节点为根。 这棵树上的每个节点 $i$ 都有其点权 $V_{i}$。 令函数 $\operatorname{Xor}(x)=\sum_{y\in \operatorname{Subtree}(x)}{V_{y}}$，其中 $\operatorname{Subtree}(x)$ 表示 $x$ 的子树。 现需支持以下五种操作： 1. `1 x`，表示将 $x$ 换为根，且查询 $\sum_{i=1}^{n}{\operatorname{Xor}(i)}$。 2. `2 x y`，表示令 $V_{x}=y$。 3. `3 x y` ，表示查询 $\operatorname{LCA}(x,y)$。 4. `4 x y`，表示查询 $x$ 到 $y$ 路径上的点的点权异或和。 5. `5 x`，表示查询 $\operatorname{Xor}(x)$。

第一行三个整数，$n,m,q$，分别表示节点数，$1$ 操作个数，其余操作个数。 接下来一行 $n$ 个整数，表示 $V_{1}\dots V_{n}$。 接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 和 $y$ 间有一条边。 接下来 $m+q$ 行，每行两到三个整数，第一个数为操作序号，接下来为相应的操作。

若干行，表示 $1,3,4,5$ 操作的结果。

对于所有数据，保证 $100\le n,m,q\le 10^6$，$0\le V_i\le 2^{31}-1$。详细数据范围如下表。 | 测试点编号 | 时间限制/秒 | $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$ |