动态树 Link-cut-tree

前置废话

顾名思义，这个科技可以用来高效维护一棵动态的树。所谓动态的树，也就是形态可以变化的树，包括加边，删边等等。

它有点像树链剖分，也是把树分成一条一条链来维护，但是因为树的形态可以变化，所以要维护上面的信息，不能用像死板一样钉在树上的线段树，而要换成更加灵活的数据结构——$Splay$！

另外一个问题来了，因为树的形态会变化，子树的大小随时都在变，重链是维护不了了，怎么办呢？$LCT$ 想了想：那么就随便分成若干条链吧。

真是方便。

进入正题

首先明确一些定义：$LCT$ 的确是乱分的链，对于每一条链，它用一棵 $Splay$ 去维护，这就导致了，这棵树本身的形态就比较混乱。

比如说，你可能有这样一棵树： 然后 $LCT$ 随手选了这样一条链： 经过 $Splay$ 的一通操作之后，树可能就变成这个样子了： 但是这不影响我们对信息的维护，往下看就明白了。

$Splay$ 里面，排序的关键字是深度，这是重点。

并且这个树还有一个特点：部分节点之间认父不认子。比如说上图中蓝色节点下面其实还有儿子，但是在 $Splay$ 里面，它并不认这个儿子，它的左右儿子都是空。但是它的这个儿子倒是热脸往冷屁股上贴，它会认这个父亲。

但是蓝色节点也很无奈，他就是想认，也不能认这个儿子，因为它所处的 $Splay$ 里面已经有一个深度为 $2$ 的节点了（橙色节点），而它的这个儿子的深度也是 $2$，一 $Splay$ 不容两个关键字相同的家伙，所以这个儿子是不可能认的。

注意，这里的深度是指原树中的深度，是指没有被魔改过的那棵树中的深度。

于是第一个操作出现了：

access 操作

既然这个链是乱造的，那么理所当然，对于一个节点 $x$，他当然也可以和根节点之间连一条链。于是，access操作出现了，它的作用是：打通根节点到某个节点 $x$ 之间的链。这当然是有代价的，这个点和根节点之间可能还有其他的链穿插于其中，这些链都要断掉为 $x$ 所用。

这是个核心函数，所以务必要认真理解。

比如说现在的有这样一棵树，红色边连接的节点是一条链，我需要打通蓝色节点到根节点的一条链。 那么事实上我的目标也就是造这样一条链： 发现中间有些点还连着一些其他的点，我们都给他断掉，就变成这样了： 我们需要断掉的红边，事实上只是往绿色的那条链外面延伸的红边，如果是在绿色的这条链里面的红边是不需要断掉的，直接使用即可，比如说上图，有一条红边就没有被删掉，也就是这条： 这种本来就连好的我们拿来用就行了，不然的话一个一个节点往上跑这样来造链的话复杂度爆炸。

代码奇短无比（为了更好地阅读下去，对于指针不大理解的读者请自行百度学习，不然下面就有点难看下去了，指针可是个好东西啊）：

void access(node *x)//打通x到根的链 { //y是用来辅助的，表示x在这条链中的儿子是谁 for(node *y=NULL;x!=NULL;y=x,x=x->fa) splay(x),x->you=y,x->check(); //先将x splay 到它所在伸展树的根位置，因为是按深度来造的树，所以它的右子树里的节点的深度都比x大 //深度比x大的节点都在绿色链的外面，我们都不要，丢掉之后把右儿子换成y，这样就完成了链的连接 }

有了这个access操作，我们就可以干很多事情了！

makeroot 操作

这个操作是将某个节点变成他所在的树的根。（不是伸展树，而是整棵树）

首先 access(x)，打通一条 $x$ 到根的链，然后 Splay(x)，让它成为他所在的 $Splay$ 的根，发现此时的树根在他的左子树里面，因为树根的深度比 $x$ 要小，那么我们将 $x$ 的左子树和右子树互换一下，那么树根就在 $x$ 的右子树里面了，这样 $x$ 就一跃成为深度最小的点了。

做完了？没有，还需要做一个 $lazy$ 标记传下去，告诉 $x$ 的子树里的节点们：他们也需要交换左右儿子，这样才能保证树的形态正常。

因为makeroot操作的本质是这样的：假如原来的树长这样：

我们 makeroot(蓝色节点) 后，相当于把蓝色节点提上来成为树根，那么树就变成了： 显然，对于这条链上所有点而言，本来深度比它小的点，现在都比他大，所以你需要造一个 $lazy$ 标记，通知 $x$ 的所有儿子节点——你们都需要交换左右儿子。

代码依然奇短无比：

void makeroot(node *x) { access(x);splay(x); x->lazy^=1;x->pushdown(); }

有了这个 makeroot 操作，接下来就更可以为所欲为了。

split 操作

现在我可以拉一条到根的链，我又可以随意指定根，那不就是说我可以随便拉一条 $x$ 到 $y$ 的链了？

void split(node *x,node *y) { makeroot(x);access(y); splay(y);//保证复杂度 }

接下来，开头上线。

link 操作

没错，这就是大家期待已久的加边操作。

具体来说，是连接两个点。一般题目都会保证（或者说有性质保证），连接的这两个点原本不连通。（不然就出现环了）

但是总有些极懒的出题人，他们的数据懒得保证，于是直接让你自己判断两点是否连通，如果连通，就不连接了。

但是实际上代码里也就只需要多一句话。

void link(node *x,node *y) { if(findroot(x)==findroot(y))return; //findroot是用来找x所在的树的根，后面会讲 //假如两点所在树的根相同，那么这两点肯定连通，就不需要连接了 makeroot(x);x->fa=y;//否则使x成为树根，然后让它的父亲变成y，这样就算连通了 //这就是认父不认子的好处，我们完全不用对y进行操作 }

假如数据保证的话，就不需要函数第一行的判断了。

那么接下来就介绍一下 findroot 操作吧。

findroot 操作

相信大家都知道怎么做了——首先access(x)，然后因为根一定是深度最小的那个，所以直接找 $x$ 所在的 $Splay$ 里面深度最小的那个就好了。也就是最左边的那个节点。

代码如下：

node *findroot(node *x) { access(x);splay(x); while(x->zuo!=NULL)x=x->zuo,x->pushdown(); splay(x);return x;//这里的splay是为了保证复杂度 }

接下来当然是删边操作了。

del 操作

删边操作也很简单，但是作为 $link$ 的双胞胎兄弟，它也对懒惰的出题人感到苦恼。

并且它比 $link$ 更加苦恼……

如果 $x$ 和 $y$ 之间有边，需要满足两个条件：

makeroot(x) , access(y) , splay(x) 后，$x$ 是不是 $y$ 的父亲，如果是，才可能有连边满足条件 $1$ 的同时，还需要 $y$ 没有左儿子（$Splay$ 中），如果没有，也就是说没有比 $y$ 的深度更小的，那么就说明 $x$ 和 $y$ 之间没有其他的点了，那么他们就肯定有直接的边相连了

假如你的 $Splay$ 维护了 $size$ ，那么就更好判断了，makeroot(x) , access(y) 之后，假如 $x,y$ 之间有直接连边，那么 $x,y$ 所在的那棵 $Splay$ 中肯定就他们两个点，直接判断 $size$ 是否等于 $2$ 即可。

代码如下：

void del(node *x,node *y) { makeroot(x);access(y);splay(x); if(y->fa!=x||y->zuo!=NULL)return; y->fa=x->you=NULL; x->check();//因为没有了一个儿子，所以需要更新一下自己维护的信息 }

你以为这就学完了？no no no，$LCT$ 里面的 $Splay$ 也是很讲究的。

Splay 的细节

因为 $LCT$ 的 makeroot 操作会给 $Splay$ 上的节点打上 $lazy$ 标记，所以每次进行 splay 操作时，先要将这些 $lazy$ 标记释放掉。然而，$lazy$ 标记只能从上往下释放，不可能从下往上的，所以你还需要弄一个栈，从需要 splay 的那个点开始往上跑，一个一个压进栈来，然后再从栈顶一个一个释放。

具体实现是这样的：

node *now=x;//新建一个点往上跑，不能直接拿x往上跑，如果拿x往上跑，那等下你splay谁？ zhan[++t]=now; while(now->notroot())zhan[++t]=now=now->fa; //notroot函数就是用来判断这个点是不是他所在的Splay的根，如果为true，就不是，如果为false，就是 while(t)zhan[t--]->pushdown();//释放lazy标记

为什么这个需要一个 notroot 函数，而不能直接判断它是不是 NULL 呢？

因为 $LCT$ 的那个性质——有些节点认父不认子，也就是说你的父亲和你不一定在一棵 $Splay$ 里面。

于是 notroot 函数的写法也就很明显了，判断一下你是不是你父亲的左右儿子即可。是的话，就返回 false，否则返回 true。

bool notroot(){return fa!=NULL&&(fa->zuo==this||fa->you==this);}

讲完了呢。

---

例题

这都是基操，没什么讲的了，就直接贴代码了。

AC code：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 100010 int n,m; struct node{ int x,sumxor,lazy; node *zuo,*you,*fa; node(int c,node *father):x(c),sumxor(c),lazy(0),zuo(NULL),you(NULL),fa(father){} void check() { sumxor=x; if(zuo!=NULL)sumxor^=zuo->sumxor; if(you!=NULL)sumxor^=you->sumxor; } void pushdown() { if(lazy) { lazy=0; swap(zuo,you); if(zuo!=NULL)zuo->lazy^=1; if(you!=NULL)you->lazy^=1; } } bool notroot(){return fa!=NULL&&(fa->zuo==this||fa->you==this);} }; node *root[maxn]; node *zhan[maxn]; int t=0; void rotate(node *x) { node *fa=x->fa,*gfa=fa->fa; if(fa->zuo==x) { fa->zuo=x->you; if(x->you!=NULL)x->you->fa=fa; x->you=fa; } else { fa->you=x->zuo; if(x->zuo!=NULL)x->zuo->fa=fa; x->zuo=fa; } fa->fa=x;x->fa=gfa; if(gfa!=NULL&&gfa->zuo==fa)gfa->zuo=x; if(gfa!=NULL&&gfa->you==fa)gfa->you=x; fa->check();x->check(); } #define witch(x) (x->fa->zuo==x) void splay(node *x) { node *now=x; zhan[++t]=now; while(now->notroot())zhan[++t]=now=now->fa; while(t)zhan[t--]->pushdown(); while(x->notroot()) { if(x->fa->notroot()&&witch(x)==witch(x->fa))rotate(x->fa),rotate(x); else rotate(x); } } void access(node *x) { for(node *y=NULL;x!=NULL;y=x,x=x->fa) splay(x),x->you=y,x->check(); } void makeroot(node *x) { access(x);splay(x); x->lazy^=1;x->pushdown(); } void split(node *x,node *y) { makeroot(x);access(y); splay(y); } node *findroot(node *x) { access(x);splay(x); while(x->zuo!=NULL)x=x->zuo,x->pushdown(); splay(x);return x; } void link(node *x,node *y) { if(findroot(x)==findroot(y))return; makeroot(x);x->fa=y; } void del(node *x,node *y) { makeroot(x);access(y);splay(x); if(y->fa!=x||y->zuo!=NULL)return; y->fa=x->you=NULL; x->check(); } void change(node *x,int y) { splay(x); x->x=y;x->check(); } int main() { scanf("%d %d",&n,&m); for(int i=1,x;i<=n;i++) scanf("%d",&x),root[i]=new node(x,NULL); for(int i=1,id,x,y;i<=m;i++) { scanf("%d %d %d",&id,&x,&y); if(id==0)split(root[x],root[y]),printf("%d\n",root[y]->sumxor); if(id==1)link(root[x],root[y]); if(id==2)del(root[x],root[y]); if(id==3)change(root[x],y); } }

更短的版本：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 100010 int n,m; struct node{ int val,z,lazy;node *zuo,*you,*fa; node(int x):val(x),z(x),lazy(0),zuo(NULL),you(NULL),fa(NULL){} void pushdown(){ if(lazy){ if(zuo)swap(zuo->zuo,zuo->you),zuo->lazy^=1; if(you)swap(you->zuo,you->you),you->lazy^=1; }lazy=0; } void pushr(){swap(zuo,you);lazy^=1;pushdown();} void pushup(){z=val;if(zuo)z^=zuo->z;if(you)z^=you->z;} bool notroot(){return fa&&(fa->zuo==this||fa->you==this);} }*rt[maxn]; void rotate(node *x) { node *fa=x->fa,*gfa=fa->fa; if(fa->zuo==x)fa->zuo=x->you,((x->you)&&(x->you->fa=fa)),x->you=fa; if(fa->you==x)fa->you=x->zuo,((x->zuo)&&(x->zuo->fa=fa)),x->zuo=fa; fa->fa=x;x->fa=gfa; fa->pushup();x->pushup(); if(gfa&&gfa->zuo==fa)gfa->zuo=x; if(gfa&&gfa->you==fa)gfa->you=x; } #define witch(x) (x->fa->zuo==x) void splay(node *x) { static node *zhan[maxn];static int t;t=0; node *now=x;zhan[++t]=now; while(now->notroot())zhan[++t]=now=now->fa; while(t)zhan[t--]->pushdown(); while(x->notroot())if(x->fa->notroot()&&witch(x)==witch(x->fa)) rotate(x->fa),rotate(x); else rotate(x); } void access(node *x){for(node *y=NULL;x;y=x,x=x->fa)splay(x),x->you=y;} void makeroot(node *x){access(x);splay(x);x->pushr();} void split(node *x,node *y){makeroot(x);access(y);splay(x);} node *findroot(node *x){access(x);splay(x);while(x->zuo)x=x->zuo;splay(x);return x;} void link(node *x,node *y){if(findroot(x)!=findroot(y))makeroot(x),x->fa=y;} void del(node *x,node *y){makeroot(x);access(y);splay(x);if(y->fa==x&&!y->zuo)y->fa=x->you=NULL,x->pushup(),y->pushup();} int main() { scanf("%d %d",&n,&m); for(int i=1,x;i<=n;i++)scanf("%d",&x),rt[i]=new node(x); for(int i=1,id,x,y;i<=m;i++) { scanf("%d %d %d",&id,&x,&y); switch(id){ case 0:split(rt[x],rt[y]);printf("%d\n",rt[x]->z);break; case 1:link(rt[x],rt[y]);break; case 2:del(rt[x],rt[y]);break; case 3:makeroot(rt[x]);rt[x]->val=y;rt[x]->pushup(); } } }

题表

[HNOI2010]弹飞绵羊   题解 国家集训队 Tree II     题解 NOI 2014 魔法森林     题解

大概还会更新的……