LCT 模板题。
要你实现树上的一些操作。
询问树上两点之间路径上点权的异或和。
连接两点，如果本来已经连通就不用。
删除两点之间的边，没有就不管。
更改某个点的权值。
这道题是 LCT 的模板题。
它主要是用类似树链剖分的样子，把边分为虚边和实边（实边只有一个）。但是它判断哪个是实边的不用看子树大小的东西，它是你想改就该的。
为什么要弄这个呢？因为这样，树上两点的路径就变成了很多个实链，就可以一个一个处理。
然后对于每一条实链，我们把它弄成一个平衡树。然后中序遍历就是要按着这个链中每个节点的深度来排。也就是说，链顶就是放在最上面，链尾就是放在最后（就是最右的位置）。
那因为本来 splay 就是断开成几个，那我们可以只开一个结构体数组来装。
那首先，你看到要求的是路径异或和，那这个在 splay 里就是一个 up 向上传递的事。
然后这里先说一说，它还要翻转两个儿子，那就要弄个懒标记，为什么要用这个后面会说。
splay 的操作
接着，我们来看如何做 splay 的两个重要操作，rotate（翻转）和 splay（上提）。
对于 rotate，它每个东西的位置都很重要，然后还要记得上传父亲的值。
对于 splay，你在弄之前要先从上到下不停地下传懒标记。
access 函数
然后你想，你要求路径异或和，那你就要让两个点都在同一个平衡树上。那如果原来不在呢？
那我们就要弄个函数把它打通，使得两点之间有实链相连。这个函数就是 。
它是怎么实现的呢？
我们这里只说打通一个点到原来的树根节点，也只会用到这个。
因为你后面还会有操作使得原来树的根节点更改。
它是这样的，我们先弄一个 记录它上一次的位置，然后我们把现在的它移到它平衡树的根的位置，然后它的右儿子就是 ，就是把这条边改成实边。那你这个改成实边，原来的实边就会被替换掉，就变成了虚边。
但是为什么原来的实边是连向右儿子的呢？
因为你平衡树的中序遍历是按实链的深度排的，那你这样找是从深度大的到深度小的，那你的 的深度就比你现在的大，那根据你的平衡树的中序遍历的排法，它就应该放在你现在的右边。那按这个意思原来的实边也会在这个地方。
然后记得把值都维护一下，然后你就可以把 改成你现在的值，你现在的值走向它的父亲，找到下一个要和它合并的平衡树。
make_root 函数
那我们刚刚说了 函数只要打通一个点到根节点就可以，因为我们可以把一个点变成原来的树的根节点。
那怎么实现呢？
我们把实现的函数叫做 函数。
那我们可以这样，先把它和根打通（这个时候它是最后的），然后把它上提到根的位置，那它就是第一个了。
但是你想想这样会造成什么改变。
因为你是根又是第一个，那它就不会有左子树。
但是你一开始是最后，所以你是不会有右子树。
那简单，把左右儿子翻转即可。
那你想想就知道当然要一直翻转下去，那就需要 lazy 懒标记了。
当然为了保险，我用的是两个的那种，就是给某个点标记的时候它的两个儿子已经翻转好了的那种。如果写这个的话记得你在这里不能只标记 lazy，还要翻转儿子。
然后你也要记得及时把 lazy 下传。
select 函数
这个函数就是要把两点之间的路径搞出来。
那我们可以先把一个点设置为根，然后把另一个点跟它的路径打通，然后再选择到它平衡树的根，那它的左儿子就是原来树的根，也就是你前面的点了。
find_root 函数
那这个其实也还好，你先打通它到根的路，然后提上去。
然后因为根中序遍历在第一个，那它肯定在最左的地方，你就直接一直向左走，就找到了。
（记得下放）
link 函数
首先，你要判断它是否已经连通，就看它们的根是否相同。
如果相同，就可以直接跳过。
否则你就可以把一个点变成根，然后让它的父亲是另一个点。然后这条边是虚边。
（因为你没有必要让它是实边，后面要实边的话后面会改的）
delete_ 函数
删去一条边。
首先我们假设一定存在这条边。
那就把路径拎出来，然后把值改成 。
原来树的根的点的父亲变成 ，另一个点的左儿子变成 。
至于为什么是左儿子……跟上面一个道理。
但是现在问题就是如何判断有没有这条边。
那如果这条边存在，那它会在实链中的一个地方出现。
那两个点的中序遍历就是相邻的。
那因为它们分别是原树的根和平衡树的根，那原树的根应该是平衡树的根的左儿子，它的父亲就是平衡树的根。
那当然，它们还要在同一个连通块。
接着你来看如何保证中序遍历相邻，或者说，要怎么样才不会相邻。
那你会想到如果原树的根有右儿子，那遍历到原树的根之后就会遍历到它的右儿子而不是平衡树的根。那就是这个情况了，那就要原树的根没有右儿子。
关于查询操作
那你考虑把它们之间的路径拎出来。
那因为这个路径就是那一条链，然后我们维护了异或和。那我们就可以直接输出这个路径的根节点里面带有的异或和，就可以了。
关于修改点权
要先把这个点提上去，再修改。
不然 Splay 信息会不正确，你提上去就只有它的异或和要改。
说的可能不是很懂，可以结合代码看看。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct Tree {
int son[2], fa, val, lazy;
}tree[200001];
int n, m, root, tot, val[200001];
int tmp[200001], x, y, op;
string s;
int read()
return re;
}
bool is_root(int now) {//判断是否是当前所在平衡树中的根节点
return tree[tree[now].fa].son[0] != now && tree[tree[now].fa].son[1] != now;
}
void down1(int now) {//向下传递lazy
swap(tree[now].son[0], tree[now].son[1]);
tree[now].lazy ^= 1;
}
void down(int now)
}
void up(int now) {//向上传递异或和的值
tree[now].val = tree[tree[now].son[0]].val ^ tree[tree[now].son[1]].val ^ val[now];
}
void rotate(int now)
void splay(int x) {//上提
tmp[0] = 1;
tmp[1] = x;
for (int i = x; !is_root(i); i = tree[i].fa)
tmp[++tmp[0]] = tree[i].fa;
while (tmp[0]) {//先从上到下下方懒标记
down(tmp[tmp[0]]);
tmp[0]--;
}
while (!is_root(x))
rotate(x);
}
up(x);
}
void access(int now)
up(now);
}
int find_root(int now) {//找到它所在平衡树的根
access(now);
splay(now);
down(now);
while (tree[now].son[0]) {//根一定在最左边
now = tree[now].son[0];
down(now);
}
return now;
}
void make_root(int now) {//把它弄成题目中的树的根
access(now);
splay(now);
down1(now);
}
void select(int x, int y) {//提取出两点之间的路径
make_root(x);
access(y);
splay(y);
}
void link(int x, int y)
void delete_(int x, int y)
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
tree[i].val = val[i];
}
for (int i = 1; i <= m; i++)
else if (op == 1) {
link(x, y);
}
else if (op == 2) {
delete_(x, y);
}
else if (op == 3) {
splay(x);
val[x] = y;
}
}
return 0;
}
