#P3282. Tree

Tree

题目描述

给定 nn 个点以及每个点的权值,要你处理接下来的 mm 个操作。操作有 44 种。操作从 00 到 33 编号。点从 11 到 nn 编号。

  1. 00:后接两个整数 xx,yy,代表询问从 xx 到 yy 的路径上的点的权值的异或和。保证 xx 到 yy 是联通的。
  2. 11:后接两个整数 xx,yy,代表连接 xx 到 yy,若 xx 到 yy 已经联通则无需连接。
  3. 22:后接两个整数 xx,yy,代表删除边 (x, y)(x,~y),不保证边 (x, y)(x,~y) 存在。
  4. 33:后接两个整数 xx,yy,代表将点 xx 上的权值变成 yy。

输入格式

第 11 行两个整数,分别为 nn 和 mm,代表点数和操作数。 第 22 行到第 n+1n + 1 行,每行一个整数,整数在 1∼1091 \sim 10^9 内,代表每个点的权值。 第 n+2n + 2 行到第 n+m+1n + m + 1 行,每行三个整数,分别代表操作类型和操作所需的量。

输出格式

对于每一个 00 号操作,你须输出 xx 到 yy 的路径上点权的异或和。

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

提示

1≤n,m≤3×1051 \le n,m \le 3 \times 10^5

题目来源

动态树