4168: 动态树 Link Cut Tree

时间限制:1000 ms 内存限制:128 MB
上传者:
提交:1 通过:1

题目描述

给定 n 个点以及每个点的权值,要你处理接下来的 m 个操作。
操作有四种,操作从 0 到 3 编号。点从 1 到 n编号。
  • 0 x y代表询问从 x 到 y 的路径上的点的权值的 xor 和。保证 x 到 y 是联通的。
  • 1 x y代表连接 x 到 y,若 x 到 y 已经联通则无需连接。
  • 2 x y代表删除边(x,y),不保证边 (x,y) 存在。
  • 3 x y代表将点 x 上的权值变成 y。


对于全部的测试点,保证:
  • 1≤n≤105,1≤m≤3×105,1≤ai≤109
  • 对于操作 0,1,2,保证1≤x,y≤n。
  • 对于操作 3,保证 1≤x≤n,1≤y≤109


PS:实际数据很弱,因为这数据太难造
原题是luogu P3690

输入格式

第一行两个整数n,m
接下来 n 行,每行一个整数,第 (i+1) 行的整数 ai 表示节点 i 的权值。
接下来 m 行,每行三个整数,分别代表操作类型和操作所需的量。

输出格式

对于每一个 0 号操作,你须输出一行一个整数,表示 x 到 y 的路径上点权的 xor 和。

输入样例 复制

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

输出样例 复制

3
1

分类标签