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

能够解决的问题:
1.求LCA
2.求最小生成树
3.维护链上信息(最大最小，链上和等)
4.维护联通性
5.维护子树信息(需要配合树)
6.优化单纯性算法，在的复杂度下求最大流（这两个是在它的论文最开头提到的，资料比较少）
（以上现在只是听过）

看别的大佬博客入门：【参考博客】
链剖分一般分为三种：
重链剖分，也就是我们常提到的“树剖”，剖分的原理是把节点个数最多的儿子当做重儿子
长链剖分，并不是很常见，可以求级祖先，原理是把深度最深的儿子当做重(长)儿子
实链剖分，也就是所用到的剖分方法

树剖的共同思想是把一棵树划分成若干条不相交的链，满足：
1.每一个点恰好属于一条链
2.在同一条链中不存在深度相同的点
这样我们就可以把两点之间的路径转化为若干条链上的区间，可以大大减小操作次数。
维护一条链，我们首先可以想到的是链表，但是用链表来维护树上权值和的话时间复杂度肯定是的，即使是块状链表也只能做到

动态树的主要时间消耗在上，而的时间复杂度是，全部操作的平摊复杂度是
树剖能做的，动态树都能做，只不过有的东西动态树做起来比树剖烦的多
LCT似乎是处理路径的，处理子树可能力不足

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int val[maxn],sum[maxn],tree[maxn][2],que[maxn],fa[maxn];
bool r[maxn];
inline bool nroot(int x) {//判断节点是否为一个Splay的根（与普通Splay的区别1）
    return tree[fa[x]][0]==x||tree[fa[x]][1]==x;
}//原理很简单，如果x与父亲连的是轻边(不在同一个splay)，他的父亲的儿子里没有它 
inline void pushup(int x) {
    sum[x]=sum[tree[x][0]]^sum[tree[x][1]]^val[x];
}//更新信息 
inline void pushr(int x) {
    int t=tree[x][0];
    tree[x][0]=tree[x][1];
    tree[x][1]=t;
    r[x]^=1;
}//翻转操作 
inline void pushdown(int x) {
    if(r[x]) {
        if(tree[x][0]) pushr(tree[x][0]);
        if(tree[x][1]) pushr(tree[x][1]);
        r[x]=false;
    }
} //释放懒标记  
inline void rotate(int x) {
    int y=fa[x],z=fa[y],k=tree[y][1]==x,w=tree[x][!k];
    if(nroot(y)) tree[z][tree[z][1]==y]=x;
    tree[x][!k]=y;//额外注意if(nroot(y))语句，此处不判断会引起致命错误（与普通Splay的区别2）
    tree[y][k]=w;
    if(w) fa[w]=y;
    fa[y]=x;
    fa[x]=z;
    pushup(y);//y的子树可能会变，x还要往上旋转 
}//一次旋转 
inline void splay(int x) {
    int top=0,y=x,z;
    que[++top]=y;//que为栈，暂存当前点到根的整条路径，pushdown时一定要从上往下放标记（与普通Splay的区别4）
    while(nroot(y)) que[++top]=y=fa[y];
    while(top) pushdown(que[top--]);
    while(nroot(x)) {
        y=fa[x];
        z=fa[y];
        if(nroot(y))
            rotate((tree[y][0]==x)^(tree[z][0]==y)?x:y);
        rotate(x);
    }//额外注意if(nroot(y))语句，此处不判断会引起致命错误（与普通Splay的区别2）即三个点的情况 
    pushup(x);
}//(使x成为该spay的根)只传了一个参数，因为所有操作的目标都是该Splay的根（与普通Splay的区别3）
inline void access(int x) {
    for(int y=0;x;x=fa[y=x]) {
        splay(x);
        tree[x][1]=y;
        pushup(x);
    }
}//打通根节点到指定节点的实链，使得一条中序遍历以根开始、以指定点结束的Splay出现
inline void makeroot(int x) {
    access(x);
    splay(x);
    pushr(x);
}//换根
inline int findroot(int x) {
    access(x);
    splay(x);
    while(tree[x][0]) {
        pushdown(x);
        x=tree[x][0];
    }
    splay(x);
    return x;
}//找根（在真实的树中的）
inline void split(int x,int y) {
    makeroot(x);
    access(y);
    splay(y);
}//提取路径  
inline void link(int x,int y) {
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;
}//连边
inline void cut(int x,int y) {
    makeroot(x);
    if(findroot(y)==x&&fa[y]==x) {
        fa[y]=tree[x][1]=0;
        pushup(x);
    }
}//断边 
int main() {
    int n=read(),m=read(),type,x,y;
    for(int i=1;i<=n;++i) val[i]=read();
    while(m--) {
        type=read(),x=read(),y=read();
        switch(type) {
            case 0:
                split(x,y);
                printf("%d\n",sum[y]);
                break;
            case 1:
                link(x,y);
                break;
            case 2:
                cut(x,y);
                break;
            case 3:
                splay(x);
                val[x]=y;//先把x转上去再改，不然会影响Splay信息的正确性
        }
    }
    return 0;
}