2539

2539. 动态树

题目

给定 $n$ 个点，编号从 $1$ 到 $n$，其中第 $i$ 个点的初始权值为 $a_i$。

现在要对这些点进行 $m$ 次操作，操作共分为以下 $4$ 种：

• 0 x y，表示询问点 $x$ 到点 $y$ 之间的路径上的所有点（包括两端点）的权值的异或和。保证 $x$ 和 $y$ 之间存在连通路径。
• 1 x y，表示在点 $x$ 和点 $y$ 之间增加一条边 $(x,y)$。注意： 如果两点已经处于连通状态，则无视该操作。
• 2 x y，表示删除边 $(x,y)$。注意： 如果该边不存在，则无视该操作。
• 3 x w，表示将点 $x$ 的权值修改为 $w$。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，表示 $n$ 个点的初始权值。

接下来 $m$ 行，每行包含一个操作，格式如题目所述。

输出格式

对于每个查询操作 0 x y，输出一个占一行的整数表示答案。

数据范围

$1 \le n \le 10^5$,

$1 \le m \le 3 \times 10^5$,

$1 \le x,y \le n$,

$x \neq y$,

$1 \le a_i,w \le 10^9$

输入样例：

3 6
1 2 3
1 1 2
1 2 3
0 1 3
2 2 3
1 1 3
0 1 3

输出样例：

0
2

题解