P3690

【模板】动态树（Link Cut Tree）

这个模板基本把 LCT 需要的操作都整全了。

一句话讲 LCT 的本质，动态维护原树的虚实链剖分，每条实链使用一棵 Splay 维护。

1. 最重要的是 Access。就是将某点到原树的根的路径上的点搞到一条实链上。具体就是不断重复：Splay，虚边变实边。

2. Makeroot 就是让某点成为原树的根。具体就是 Access 之后，颠倒辅助树中的这棵 Splay 对原树深度关系的描述，而 Splay 描述深度关系是依靠于 Splay 的中序遍历的顺序的，因此颠倒深度关系就是把这颗 Splay 翻转一下。

3. Find 是找树根。先 Access，然后 Splay 一下，那原树的树根就是最左边的点。最后要再 Splay 一次保证复杂度。

4. Split 是抽出 $x$ 到 $y$ 的路径。先 Makeroot $x$，然后 Access $y$，再 Splay $y$ 即可。这样 $x$ 到 $y$ 的路径信息就是 $y$ 所在的 Splay 的信息。

5. Link 先需要判断是否连通，就是判断 Find 是否相同。然后我们 Makeroot $x$ 再 Splay $x$，这样 $x$ 就成为了原树的树根，我们将 $x$ 向 $y$ 连一条虚边即可。

6. Cut 先需要判断在同一棵原树里，也是判断 Find。然后 Split $x$ 和 $y$。然后我们要判断是否有边连着 $x$ 和 $y$。首先由上我们知道 $x$ 和 $y$ 已经保证连通了，并且经过了 Split 导致 $x$ 成为原树的根（意味着它一定在 $y$ 现在的左子树里）。那么如果保证两者有边相连，则其深度一定是连续的，所以 $x$ 不能再有右子树，$y$ 的左儿子就是 $x$。判断一下之后，把边双向断开即可。

7. Splay 和 Rotate 与 Splay 的操作基本相同，但是注意现在的根不是真的根，而是对于单个 Splay 的根。所以我们要写一个 Isroot 函数方便判断。

这两个操作里有一些小坑，首先，Rotate 中要在旋转之前就把 $z$ 与 $x$ 的关系定下，不然马上 Rotate 之后改变了树的关系，原本的虚边就被转成实边了，而这显然是不可以的。

其次，Splay 之前要先把翻转路径上 Splay 的翻转标记全部下放。

稍微修了一下代码，只有不到 90 行。

你看 LCT 比 Splay 还好写。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,op,x,y;

ll buffa[N+5],bufch[2][N+5],bufxr[N+5],bufval[N+5];
bool bufrev[N+5];
ll *nowfa=buffa,*nowch[2]={bufch[0],bufch[1]},*nowxr=bufxr,*nowval=bufval;
bool *nowrev=bufrev;

struct LCT{
  ll *fa,*ch[2],*xr,*val;bool *rev;
  inline void Init(ll x) {
    ch[0]=nowch[0];ch[1]=nowch[1];fa=nowfa;xr=nowxr;val=nowval;rev=nowrev;
    nowch[0]+=x+1;nowch[1]+=x+1;nowfa+=x+1;nowxr+=x+1;nowval+=x+1;nowrev+=x+1;
  }
  inline void Pushup(ll x) {xr[x]=xr[ch[0][x]]^xr[ch[1][x]]^val[x];}
  inline void Pushdown(ll x) {
    if(rev[x]) {
      rev[ch[0][x]]^=1;rev[ch[1][x]]^=1;swap(ch[0][x],ch[1][x]);rev[x]=0;
    }
  }
  inline ll Get(ll x) {return x==ch[1][fa[x]];}
  inline ll Isroot(ll x) {return ch[0][fa[x]]!=x&&ch[1][fa[x]]!=x;}
  inline void Update(ll x) {if(!Isroot(x)) Update(fa[x]);Pushdown(x);}
  inline void Rotate(ll x) {
    ll y=fa[x],z=fa[y],c=Get(x);if(!Isroot(y)) ch[y==ch[1][z]][z]=x;
    ch[c][y]=ch[c^1][x];if(ch[c^1][x]) fa[ch[c^1][x]]=y;
    ch[c^1][x]=y;fa[y]=x;fa[x]=z;Pushup(y);Pushup(x);
  }
  inline void splay(ll x) {
    Update(x);
    for(ll f;f=fa[x],!Isroot(x);Rotate(x)) {
      if(!Isroot(f)) Rotate(Get(f)==Get(x)?f:x);
    }
  }
  inline ll Access(ll x) {
    ll p=0;for(;x;p=x,x=fa[x]) {splay(x);ch[1][x]=p;Pushup(x);}return p;
  }
  inline void Makeroot(ll x) {Access(x);splay(x);rev[x]^=1;}
  inline ll Find(ll x) {
    Access(x);splay(x);Pushdown(x);
    while(ch[0][x]) {x=ch[0][x];Pushdown(x);}splay(x);return x;
  }
  inline void Split(ll x,ll y) {Makeroot(x);Access(y);splay(y);}
  inline void Link(ll x,ll y) {Makeroot(x);fa[x]=y;}
  inline void Cut(ll x,ll y) {
    Split(x,y);if(ch[0][y]==x&&ch[1][x]==0) ch[0][y]=fa[x]=0;
  }
  inline void Fix(ll x,ll y) {Access(x);splay(x);val[x]=y;Pushup(x);}
}T;

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
  while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar('-');do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar('\n');}

int main() {

  n=read();m=read();T.Init(n);

  for(ll i=1;i<=n;i++) {T.xr[i]=T.val[i]=read();}

  while(m--) {
    op=read();x=read();y=read();
    if(op==0) {T.Split(x,y);writeln(T.xr[y]);}
    if(op==1) {ll xx=T.Find(x),yy=T.Find(y);if(xx!=yy) T.Link(x,y);}
    if(op==2) {ll xx=T.Find(x),yy=T.Find(y);if(xx==yy) T.Cut(x,y);}
    if(op==3) {T.Fix(x,y);}
  }

  return 0;
}