Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

01/7
11:10
LCT 图论

BZOJ 3282 Tree LCT

Description

给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从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。

Input

第1行两个整数,分别为N和M,代表点数和操作数。 第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。 第N+2行到第N+M+1行,每行三个整数,分别代表操作类型和操作所需的量。

Output

对于每一个0号操作,你须输出X到Y的路径上点权的Xor和。

Sample Input

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

Sample Output

3
1

HINT

1<=N,M<=300000

Source

动态树

 

 

LCT的板子题……