题解 P3690 【【模板】Link Cut Tree （动态树）】
Link-Cut-Tree
前置芝士：Splay 推荐先做文艺平衡树
为什么要用Splay呢？因为我们要支持区间翻转（目前我所见到的区间翻转用到的基本上都是Splay和FHQSplay太强了！！！）
LCT属于树链剖分，确切地讲应该是实链剖分。 类似于重链剖分，不再过多赘述懒。LCT维护的是森林的连通性问题，这也就是为什么他叫Link（链接）-Cut（切断）-Tree（树森林）的原因。并且我们用Splay来维护一条实路径。Splay的大小标准是每个点的深度。
直接开讲。。。
LCT最核心操作，Access（x），打通从x到他所在树的根结点的路径（使这条路径上全是实边）。这个操作太重要了。。。怎么写呢？
不断跳fa，并父子相认（就是把这条路径变为了实边）。
inline void access(node *x) {for(node *y = NULL;x;x = (y = x) -> fa) splay(x) , x -> ch[1] = y , x -> up();}makeroot（x），把这个点变为根，就是要把他到原根节点的路径翻转，肯定不能暴力，于是用到Splay打标记（记得下放哦，不然会死的很惨！！！）。 先用access开路，splay转到根节点，直接打上标记，完事。
inline void makeroot(node *x) { access(x); splay(x); x -> tag ^= 1;}findroot，找到根节点。access开路，splay转上去，根的深度一定是最小的，那么不断找左儿子就行了。
inline node *findroot(node *x)
{
access(x) , splay(x);
while(x -> down() , x -> ch[0]) x = x -> ch[0];
return x;
}link，连接两个点，让一个点为根，再让另一个点当他的fa就行了
inline void link(node *x,node *y)
{
if(findroot(x) == findroot(y)) return;
makeroot(x); x -> fa = y;
}cut，切断一条边，让x成为根，access（y），则y一定是x的儿子，再把ysplay上去，x一定是y的左儿子，父子不相认即可。
inline void cut(node *x,node *y)
{
makeroot(x); access(y); splay(y);
if(y -> ch[0] == x) y -> ch[0] = x -> fa = NULL;
}修改，维护splay即可。
inline void chenge(node *x,int y) {splay(x); x -> val = y; x -> up();}
inline int query(node *x,node *y) {makeroot(x); access(y); splay(y); return y -> sum;}完整代码如下：
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100005;
inline int read()
{
int x = 0 , f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n , m;
struct Link_Cut_Tree
{
struct node
{
node *ch[2] , *fa;
int val , sum , tag;
node(int val = 0,int sum = 0,int tag = 0) : val(val) , sum(sum) , tag(tag) {ch[0] = ch[1] = fa = NULL;}
inline bool ntr() {return fa && (fa -> ch[0] == this || this == fa -> ch[1]);}
inline bool isr() {return this == fa -> ch[1];}
inline void up()
{
sum = val;
if(ch[0]) sum ^= ch[0] -> sum;
if(ch[1]) sum ^= ch[1] -> sum;
}
inline void down()
{
if(!tag) return;
swap(ch[0],ch[1]);
if(ch[0]) ch[0] -> tag ^= 1;
if(ch[1]) ch[1] -> tag ^= 1;
tag = 0;
}
}*root[N] , *st[N];
int top = 0;
inline void rot(node *x)
{
bool k = x -> isr();
node *y = x -> fa , *z = y -> fa , *w = x -> ch[!k];
if(y -> ntr()) z -> ch[y -> isr()] = x;
x -> ch[!k] = y; y -> ch[k] = w;
y -> fa = x; x -> fa = z;
if(w) w -> fa = y;
y -> up(); x -> up();
}
inline void splay(node *x)
{
st[top = 1] = x;
while(st[top] -> ntr()) st[top + 1] = st[top] -> fa , top ++;
while(top) st[top --] -> down();
while(x -> ntr())
{
if(x -> fa -> ntr()) rot(x -> isr() ^ x -> fa -> isr() ? x : x -> fa);
rot(x);
}
}
inline void access(node *x) {for(node *y = NULL;x;x = (y = x) -> fa) splay(x) , x -> ch[1] = y , x -> up();}
inline void makeroot(node *x) { access(x); splay(x); x -> tag ^= 1;}
inline node *findroot(node *x)
{
access(x) , splay(x);
while(x -> down() , x -> ch[0]) x = x -> ch[0];
return x;
}
inline void link(node *x,node *y)
{
if(findroot(x) == findroot(y)) return;
makeroot(x); x -> fa = y;
}
inline void cut(node *x,node *y)
{
makeroot(x); access(y); splay(y);
if(y -> ch[0] == x) y -> ch[0] = x -> fa = NULL;
}
inline void chenge(node *x,int y) {splay(x); x -> val = y; x -> up();}
inline int query(node *x,node *y) {makeroot(x); access(y); splay(y); return y -> sum;}
inline void LOL()
{
n = read(); m = read();
for(int i = 1 , val;i <= n;i ++) { val = read();root[i] = new node(val,val);}
for(int i = 1 , opt , x , y;i <= m;i ++)
{
opt = read(); x = read(); y = read();
if(opt == 0) printf("%d\n",query(root[x],root[y]));
if(opt == 1) link(root[x],root[y]);
if(opt == 2) cut(root[x],root[y]);
if(opt == 3) chenge(root[x],y);
}
}
}DNF;
int main()
{
DNF.LOL();
return 0;
}