P3690 【Template】Dynamic Tree (LCT)

Given $n$ nodes and each node’s weight, you need to process the next $m$ operations. There are four types of operations, numbered from $0$ to $3$. Nodes are numbered from $1$ to $n$. - `0 x y` asks for the $\text{xor}$ sum of the weights of the nodes on the path from $x$ to $y$. It is guaranteed that $x$ and $y$ are connected. - `1 x y` connects $x$ to $y$. If $x$ and $y$ are already connected, do nothing. - `2 x y` deletes the edge $(x, y)$. The existence of edge $(x, y)$ is not guaranteed. - `3 x y` sets the weight of node $x$ to $y$.

The first line contains two integers $n$ and $m$, representing the number of nodes and the number of operations. The next $n$ lines each contain one integer. On the $(i + 1)$-th line, the integer $a_i$ denotes the weight of node $i$. The next $m$ lines each contain three integers, representing the operation type and its parameters.

For each operation of type $0$, output one line with one integer, the $\text{xor}$ sum of the node weights on the path from $x$ to $y$.

Constraints and Conventions For all testdata, it is guaranteed that: - $1 \leq n \leq 10^5$, $1 \leq m \leq 3 \times 10^5$, $1 \leq a_i \leq 10^9$. - For operations $0, 1, 2$, it holds that $1 \leq x, y \leq n$. - For operation $3$, it holds that $1 \leq x \leq n$, $1 \leq y \leq 10^9$. Translated by ChatGPT 5