题解 P3690 【模板】Link Cut Tree (动态树)

题目描述

给定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。

输入输出格式

输入格式:
第1行两个整数,分别为n和m,代表点数和操作数。

第2行到第n+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。

第n+2行到第n+m+1行,每行三个整数,分别代表操作类型和操作所需的量。

输出格式:
对于每一个0号操作,你须输出x到y的路径上点权的xor和。

输入输出样例

输入样例#1:
3 3
1
2
3
1 1 2
0 1 2
0 1 1
输出样例#1:
3
1

说明

数据范围:$ 1 \leq N, M \leq 3 \cdot {10}^5 1≤N,M≤3?10^5 $

Solution

发表评论