与图论的邂逅04：LCT

　　本着对数据结构这一块东西的一股兴趣，最近在集训的百忙之中抽空出来学LCT，终于学懂了这个高级玩意儿。

---

前置知识：Splay和树链剖分

　　Splay挺复杂的......这里就先不写，不然篇幅太大。树链剖分倒是可以大致地讲一下。

树链剖分

　　什么是树链剖分呢？就是把树给解剖成一条条的链子啦~那就先从最常用的重链剖分讲起。对于当前节点u和它的儿子构成的点集V，若size[v]=max{size[w] | w∈V}，也就是以u的儿子为根的所有子树中size最大的那个儿子是v，那么称v是u的重儿子(定义size[x]：以x为根的子树所含有的点数)。如果这时把u向v连一条边，并且其它所有点也像这么做(连向它们的重儿子，叶子节点除外)，由于重儿子唯一，父亲唯一，所以就会形成一条一条的链。这个链就叫重链。重链剖分是如此，类比一下就能够理解长链剖分：每个点连向子树深度最大的那个儿子。然而这两种剖法都不是LCT所使用的。LCT使用的是：实链剖分。

　　实链剖分就是说，把某个节点向它的某个儿子连实边，向其它儿子连虚边，这样也能连出一条条链子。实链剖分有什么好处呢？重链剖分和长链剖分中的size和dep都是固定的，也就是说剖完一棵树之后就无法再改变。而注意刚才实链剖分定义中的一句话："把某个节点向它的某个儿子连实边"，也就是说这个"某个儿子"是可以改变的。那么实链剖分就应运而生并用于解决更灵活的问题。

　　如果你觉得还不清楚，你可以看一下苯蒟蒻对重链剖分一点点浅显的理解：https://www.cnblogs.com/akura/p/10692600.html，然后类比地这些链剖分应该就可以理解了。

---

LCT

　　LCT使用Splay作为辅助树来维护实链，其Splay平衡的关键字为深度。也就是说，右边的点深度大于根，左边的点深度小于根。下面是LCT的相关操作：

access(x)

　　指打通x到根节点之间的路径，即建立一条从根节点连向x的实链。只需要从x一个链子一个链子地往上跳，并且把跳到的链子改一下即可。原本x到根节点路径上的点可能属于其它的实链，也就是说它的儿子不在x到根节点的路径上——这时把这对父子关系的边断掉即可：

　　图中粗的是Splay维护的实链，细的是轻边。access之后成了这个样子：

　　也就是说，我往上连链子的时候碰到一个点，我不管它之前连的哪条链子，都给他断掉，连上我要的链子。

inline void access(int x){ for(int y=;x;ch[x][]=y,update(x),x=fa[y=x]) splay(x); }

　　每次把x旋到当前Splay的根节点处，往上连边。由于改变了Splay，所以要update一下。

makeroot(x)

　　指让x成为当前的根。很简单，只需打通x到根节点的路径，然后用splay把x旋到链子顶端即可。最后不要忘了reverse(因为dep发生了改变)。

　　这是access之后x和根节点之间的实链；

　　这是splay了并且reverse过的这条链子。

inline void makeroot(int x){ access(x),splay(x),rev(x); }
//rev为reverse

split(x,y)

　　指打通x到y的路径。先用makeroot(x)让x成为树根，然后用access(y)打通y到根节点(也就是x)的路径即可。最后为了保证复杂度，把y节点splay一下。

　　然后makeroot(x)。

　　再access。

　　最后splay一下，就不画了。(splay的部分都不画了吧......太麻烦)

inline void split(int x,int y){ makeroot(x),access(y),splay(y); }

findroot(x)

　　寻找x所在原树的树根。先access(x)打通根到x的路径，然后splay把x旋到Splay的根。此时树的形态发生改变，所以要下传标记。由于根的深度是最小的，所以此时从x开始往Splay的左儿子一直走，最后走到的点就是根。为了保证复杂度，最后再splay一下根。

inline int findroot(int x){ access(x),splay(x),down(x); while(ch[x][]) x=ch[x][],down(x); return splay(x),x; }

link(x,y)

　　从x往y连一条边。首先makeroot(x)让x成为根，此时link(x,y)是合法的当且仅当findroot(y)!=x即y所在原树的根不是x。这时只需让fa[x]=y即可。不要忘了update(y)更新一下儿子的信息。

inline void link(int x,int y){ makeroot(x); if(findroot(y)!=x) fa[x]=y,update(y); }

cut(x,y)

　　切断x与y之间的边。首先还是makeroot(x)让x成为根，此时cut(x,y)是合法的当且仅当findroot(y)=x并且fa[y]=x并且ch[y][0]=0。最后一个条件是什么意思呢？由于Splay中左儿子的深度小于根，所以若ch[y][0]不为0，则说明还有比y深度更小的点介于x与y之间，此时不能删边。判断合法之后，修改两个节点的信息，令ch[x][1]=0,fa[y]=0即可。还是不要忘了更新一下x的儿子的信息。

inline void cut(int x,int y){ makeroot(x); if(findroot(y)==x&&fa[y]==x&&!ch[y][]) ch[x][]=fa[y]=,update(x); }

---

　　以上就是LCT的最基础的操作(苯蒟蒻还没有学其它的高级操作)。难理解的部分都画了图，应该是能看懂的。

　　最后对着模板题放个代码：

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

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 300001
using namespace std;
typedef long long ll;

inline int read(){
    register int x(),f(); register char c(getchar());
    while(c<''||''<c){ if(c=='-') f=-; c=getchar(); }
    while(''<=c&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
    return x*f;
}
inline void swap(ll &a,ll &b){ register int tmp; tmp=a,a=b,b=tmp; }

int  ch[maxn][],fa[maxn],lz[maxn];
ll sum[maxn],val[maxn];

inline int isroot(int x){ return ch[fa[x]][]==x||ch[fa[x]][]==x; }
inline int getson(int x){ return ch[fa[x]][]==x; }
inline void update(int x){ sum[x]=val[x]^sum[ch[x][]]^sum[ch[x][]]; }
inline void rev(int x){ lz[x]^=; swap(ch[x][],ch[x][]); }
inline void down(int x){ if(lz[x]){ if(ch[x][]) rev(ch[x][]); if(ch[x][]) rev(ch[x][]); } lz[x]=; }
inline void rotate(int x){
    int y=fa[x],z=fa[y],k=getson(x),w=ch[x][k^];
    if(isroot(y)) ch[z][getson(y)]=x;fa[x]=z;
    ch[x][k^]=y,fa[y]=x;
    if(w) fa[w]=y; ch[y][k]=w;
    update(y);
}
inline void splay(int x){
    int y,z,stack[maxn]; y=x,z=,stack[++z]=y;
    while(isroot(y)) y=fa[y],stack[++z]=y; while(z) down(stack[z--]);
    for(y=fa[x]; isroot(x); rotate(x),y=fa[x]) if(isroot(y)) rotate(getson(y)^getson(x)?x:y); update(x);
}

inline void access(int x){ for(int y=;x;ch[x][]=y,update(x),x=fa[y=x]) splay(x); }
inline void makeroot(int x){ access(x),splay(x),rev(x); }
inline void split(int x,int y){ makeroot(x),access(y),splay(y); }
inline int findroot(int x){ access(x),splay(x),down(x); while(ch[x][]) x=ch[x][],down(x); return splay(x),x; }
inline void link(int x,int y){ makeroot(x); if(findroot(y)!=x) fa[x]=y,update(y); }
inline void cut(int x,int y){ makeroot(x); if(findroot(y)==x&&fa[y]==x&&!ch[y][]) ch[x][]=fa[y]=,update(x); }

int main(){
    int n=read(),m=read();
    for(register int i=;i<=n;i++) sum[i]=val[i]=read();
    for(register int i=;i<=m;i++){
        int op=read(),x=read(),y=read();
        if(op==) split(x,y),printf("%lld\n",sum[y]);
        if(op==) link(x,y);
        if(op==) cut(x,y);
        if(op==) splay(x),val[x]=y;
    }
    return ;
}