动态树 LCT (Link - Cut - Tree)

一、什么是 LCT ？

先给出一道题：

给出一棵树，每个点都有点权，要求进行一些操作：

将树上两个点间的简单路径上的点的点权加上某个数
统计树上两个点间的简单路径上的点的点权之和

很显然，这是一道树链剖分的模板题，只需要求出每个点的重儿子就行了（重儿子是指其子树节点数最多的一个儿子）。

然而，倘若我们增加两种操作：连边与断边。使这个问题由一棵树上的操作变成一片森林的操作，树链剖分就不管用了，那么这时，我们该怎么办呢？

相信你已经想到了，那就是我们今天的主角—— LCT ！

动态树，顾名思义，就是一种用对数复杂度处理一些形态会改变的树上问题。非常的好用。

二、LCT 的原理

1. 建立辅助树

LCT 的原理很简单，简单概括就是 splay 树 + 树链剖分。倘若再进行连边与断边操作时，我们直接在原树上修改，就会影响我们先前做的处理，导致我们很难统计链上的信息。

因此我们建立一棵辅助树，使得原树与辅助树能够相互转换，就能够通过改变辅助树来改变原树的形态。

那么这棵辅助树该怎么建呢？

实际上我们还是使用树链剖分，不过由于树的结构是变化的，所以提前剖好所有的链没有意义，因此这里的树链剖分既不是重链剖分，也不是长链剖分。

我们给出一棵树。

对它进行剖分，我们把剖出的边（加粗的）称为实边，其余的称为轻边，其中多条实边可以构成实链（注意：实边不一定要覆盖整棵树，也可以整棵树没有一条实边，全都是轻边）

在剖好链之后，我们将每条实链的节点按从上到下的顺序建一棵 splay 树，其中 splay 树的中序遍历就是原树实链上从上到下的顺序，比如原树上的

1 - 2 - 4

这条实链，建好后就长这样。

再比如

6 - 9

这条链，建好后就长这样。

但是，现在还有一个问题，原树上的轻边怎么办呢？很简单，直接挂上去就行了，就比如说

1 - 2 - 4

这条实链中

1

还有一条轻边连接

3

，直接在辅助树上连接。

不过，实际上辅助树不应该这么连，因为

3

在他所在的 splay 树上有它自己的父亲(除非它在 splay 树上是根节点)因此，应该将

1

与

3

所在 splay 树上的根节点连边。

通过这些方法，我们就能建出辅助树，容易发现，由辅助树的形态可以还原出原树的形态，因此我们接下来直接在辅助树上操作就可以了。

2. $\text{access}(x)$ 操作

\text{access}(x)

操作是 LCT 的核心操作之一，它的作用是在原树上建一条以原树根节点为起点，以

x

为终点的一条实链。（注意：不改变原树的形态）

举个例子：

\text{access}(9)

首先，我们将

9

旋转到它所在 splay 树的根，并断开与右儿子的联系。不过这里没有右儿子。

其次，我们将

9

现在的父节点

3

（也是它在原树上的父节点）旋转到它所在 splay 树的根并将右儿子替换为

9

。

（为什么是右儿子？因为 $9$ 在原树上比 $3$ 深度多 $1$ ，因此在 splay 树上的中序遍历顺序也应该比 $3$ 多 $1$ ，也就是成为 $3$ 的右儿子）

然后我们再不断进行以上操作直到找到根节点，这样，我们就建出一条起点为原树根节点，终点为

9

的一条实链了。

3. $\text{reverse}(x)$ 操作

\text{reverse}(x)

操作在原理和实现上都非常简单，它的作用是将以

x

为根的一棵 splay 树内部的所有结点的左右儿子全部翻转（对应到原树上就是将一条实链从上到下全部翻转）

实现很简单，在

x

打个翻转的懒标记，后面执行其他操作时将标记下传就行了。

我们以初始辅助树，

\text{reverse}(2)

为例

4. $\text{makeroot}(x)$ 操作

\text{makeroot}(x)

操作也是 LCT 的核心操作之一，它的作用是将一个节点在原树上翻转到根。

\text{makeroot}(x)

的实现并不难，我们先进行

\text{access}(x)

操作，建一条从根到

x

的实链，再把

x

在辅助树上旋转到根，最后进行

\text{reverse}(x)

操作就可以了。（原本根在链顶端， $x$ 在链底端，翻转之后 $x$ 在链顶端，原本的根在链底端，相当于把 $x$ 替换到根的位置）

对应到原树上就是这样

5. $\text{split}(x,y)$ 操作

\text{split}(x,y)

操作的功能和

\text{access}(x)

操作类似，不过它的功能是在辅助树上建立起一条起点为

x

，终点为

y

的一条实链。

很容易想到，

\text{access}(x)

操作和

\text{split}(x)

操作类似，因此可以借助

\text{access}(x)

来实现

\text{split}(x,y)

操作。

首先，我们进行

\text{makeroot}(x)

操作，使原树的根变为

x

，再进行一次

\text{access}(y)

操作，由于此时原树的根为

x

因此

\text{access}(y)

操作相当于建立一条起点为

x

，终点为

y

的一条实链，最后执行

\text{splay}(y)

，把

y

旋转到这条实链的根，方便后续操作。

我们以

\text{split}(9,5)

为例：

6. $\text{link}(x,y)$ 操作与 $\text{cut}(x,y)$ 操作

接下来，就到我们最关心的内容了，连边操作与断边操作！！ 这也是 LCT 相比于普通树链剖分的优势。

\text{link}(x,y)

意思就是将原树上的

x

，

y

之间连一条边，实现这个操作一点儿也不复杂。

我们现在加入一个新节点

10

，以

\text{link}(9,10)

为例：

首先

\text{makeroot}(9)

，将

9

翻转到它所在的树的根，由于它此时为根节点，因此它现在的父亲为

0

，于是我们令

9

的父亲为

10

，便不会改变树上维护的信息。

对应到原树上就是这样

\text{cut}(x,y)

的作用与

\text{link}(x,y)

的作用相反，作用是将原树上

x

，

y

之间的边断开，

\text{cut}(x,y)

的实现比

\text{link}(x,y)

复杂一些，为了方便操作，我们在原树上建一条从

x

到

y

的实链，此时，

x

，

y

直接相连，因此，在这条实链对应的 splay 树上，

x

为

y

的左儿子且

x

没有右儿子。（如果不是，则说明 $x$ 和 $y$ 在原树上没有连边，直接退出）

如果

x

，

y

在原树上有连边，则直接断开

x

，

y

之间的联系，让

x

成为他所在树上的根，并更新

y

所记录的这条实链上的信息。

我们使用刚才

\text{link}(9,10)

之后的树，以

\text{cut}(9,10)

为例：

对应到原树上就是这样

7. 信息维护

LCT 上的信息是在实链内维护的，一条实链对应的 splay 树上的根节点维护这条实链上的信息，这也导致了 LCT 的缺点：只能处理链上的信息，而不能处理子树的信息。 如果想要维护子树上的信息，就只能使用更高级的动态树 SATT(Self - Adjusting Top Tree)。

8. 其他函数

除了上述重要函数外，还有

\text{findroot}(x)

等函数，在后面的程序实现中会介绍的。

三、时间复杂度

以下证明来源于oi-wiki

因为 LCT 中所有操作皆以

\text{access}

操作为基本操作，因此我们只需求出

\text{access}

操作的平摊复杂度，就能得到 LCT 所有操作的平摊复杂度。

\text{access}

操作的时间复杂度主要来源于

\text{splay}

操作与虚实链转换。

\text{splay}

操作

由 splay 树的时间复杂度分析易知， $\text{splay}$ 操作的均摊时间复杂度为 $O(\log n)$

2.虚实链转换

参考树链剖分，定义两种虚边：

重虚边： $v$ 连向父亲的虚边，其中 $size(v)\ge \frac{1}{2} size(parent(v))$
轻虚边： $v$ 连向父亲的虚边，其中 $size(v)\le \frac{1}{2} size(parent(v))$

对于虚边的处理，可以使用势能分析，定义势能函数

\Phi

为所有重虚边的数量，定义均摊成本

c_i = t_i + \Delta \Phi_i

，其中

𝑡_𝑖

为实际操作的成本，

\Delta \Phi_i

为势能的变化。

走过重虚边后，会将重虚边转换为实边，该操作会减少 1 的势能，因为它通过加强重要连接来优化树的结构。且由于其实际操作成本为 $𝑂(1)$ ，抵消了势能的增加，故不会增加均摊成本，所有的均摊成本集中在轻虚边的处理上。
每次 $\text{access}$ 操作最多遍历 $O(\log n)$ 条轻虚边，因此至多消耗 $O(\log n)$ 的实际操作成本，转化得到 $O(\log n)$ 条重虚边，即势能以 $O(\log n)$ 的代价增加。

由此，最终访问虚边的均摊复杂度为实际操作成本和势能变化的和，即

O(\log n)

。

综上所述，LCT 中

\text{access}

操作的时间复杂度是

\text{splay}

操作和虚边访问的复杂度之和，因此最后的均摊复杂度为

O(\log n)

。

四.程序实现

1.结构体定义

CPP

#include<bits/stdc++.h>
#define ls ch[0]
#define rs ch[1]
using namespace std;
struct stu{
	int fa,ch[2];
  //虚边中子节点指向父亲，但父节点不指向儿子
  //只有实边的父亲儿子才会互相记录
	int val,sum;
	int tag;//reserve操作的翻转标记
}t[N];

2. $\text{isroot}$ 操作（查找某节点是否为该节点所在 splay 树的根）

CPP

bool isroot(int u){return t[t[u].fa].ls!=u&&t[t[u].fa].rs!=u;}
//当此节点为splay树的根时，它的父亲不会记录它

3. $\text{pushup}$ 操作（信息上传）

CPP

void pushup(int u){
	t[u].sum=t[t[u].ls].sum+t[t[u].rs].sum+t[u].val;
}

4. $\text{reserve}$ 操作（翻转左右子树）

CPP

void reverse(int u){
	if(!u)return;
	swap(t[u].ls,t[u].rs);//翻转左右子树
	t[u].tag^=1;//打标记
}

5. $\text{pushdown}$ 操作（标记下传）

CPP

void pushdown(int u){
	if(t[u].tag){
		reverse(t[u].ls);
		reverse(t[u].rs);
		t[u].tag=0;
	}
}

6. $\text{push}$ 操作（标记全部下传）

CPP

void push(int u){
	if(!isroot(u))push(t[u].fa);
  //一定要先遍历父亲再下传，否则父亲标记残留可能导致信息下传错误
	pushdown(u);
}//为后续splay准备

7. $\text{rotate}$ 操作

CPP

void rotate(int u){
	int f=t[u].fa;
	int g=t[f].fa;
	int k=(u==t[f].rs);
	if(!isroot(f)){
		if(t[g].ls==f)t[g].ls=u;
		else t[g].rs=u;
	}
	t[u].fa=g;
	t[f].ch[k]=t[u].ch[k^1];
	if(t[u].ch[k^1])t[t[u].ch[k^1]].fa=f;
	t[u].ch[k^1]=f;
	t[f].fa=u;
	pushup(u),pushup(f);//更新链上信息
}

8. $\text{splay}$ 操作

CPP

void splay(int u){
	push(u);
	while(!isroot(u)){
		int f=t[u].fa,g=t[f].fa;
		if(!isroot(f)){
			if((t[f].ls==u)==(t[g].ls==f))rotate(f);
			else rotate(u);
		}
		rotate(u);
	}
	pushup(u);//更新链上信息
}

9. $\text{access}$ 操作

CPP

void access(int u) {
    for(int child=0;u;child=u,u=t[u].fa)//让原先的u成为儿子，建立实边
    {
        splay(u);//将当前节点u旋转到其所在辅助助树的根位置
        t[u].ch[1] = child;//将u的右孩子设为child
        pushup(u);//更新链上信息
    }
}

10. $\text{makeroot}$ 操作

CPP

void makeroot(int u){
	access(u),splay(u),reverse(u);
}

11. $\text{split}$ 操作

CPP

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

12. $\text{link}$ 操作

CPP

void link(int x,int y){
	makeroot(x),t[x].fa=y;
}//连边时一定要判断两点是否连通！否则会产生环。

13. $\text{cut}$ 操作

CPP

void cut(int x,int y){
	split(x,y);
	if(t[y].ch[0]!=x||t[x].ch[1])return;//x和y之间没有连边
	t[x].fa=t[y].ch[0]=0;
	pushup(y);
}

14. $\text{findroot}$ 操作（查找节点所在树上的根）

CPP

int findroot(int u){
	access(u),splay(u);//access(u)后链的顶端就是根
	while(t[u].ls)u=t[u].ls;
	return u;
}

所有函数

CPP

#include<bits/stdc++.h>
#define ls ch[0]
#define rs ch[1]
using namespace std;
const int N=3e5+5;
int n,m,k,x,y;
struct stu{
	int fa,ch[2];
	int val,sum;
	int tag;
}t[N];
bool isroot(int u){return t[t[u].fa].ls!=u&&t[t[u].fa].rs!=u;}
void pushup(int u){
	t[u].sum=t[t[u].ls].sum+t[t[u].rs].sum+t[u].val;
}
void reverse(int u){
	if(!u)return;
	swap(t[u].ls,t[u].rs);
	t[u].tag^=1;
}
void pushdown(int u){
	if(t[u].tag){
		reverse(t[u].ls);
		reverse(t[u].rs);
		t[u].tag=0;
	}
}
void push(int u){
	if(!isroot(u))push(t[u].fa);
	pushdown(u);
}
void rotate(int u){
	int f=t[u].fa;
	int g=t[f].fa;
	int k=(u==t[f].rs);
	if(!isroot(f)){
		if(t[g].ls==f)t[g].ls=u;
		else t[g].rs=u;
	}
	t[u].fa=g;
	t[f].ch[k]=t[u].ch[k^1];
	if(t[u].ch[k^1])t[t[u].ch[k^1]].fa=f;
	t[u].ch[k^1]=f;
	t[f].fa=u;
	pushup(u),pushup(f);
}
void splay(int u){
	push(u);
	while(!isroot(u)){
		int f=t[u].fa,g=t[f].fa;
		if(!isroot(f)){
			if((t[f].ls==u)==(t[g].ls==f))rotate(f);
			else rotate(u);
		}
		rotate(u);
	}
	pushup(u);
}
void access(int u){
	for(int child=0;u;child=u,u=t[u].fa){
		splay(u);
		t[u].ch[1]=child;
		pushup(u);
	}
}
void makeroot(int u){
	access(u),splay(u),reverse(u);
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}
void link(int x,int y){
	makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
	split(x,y);
	if(t[y].ch[0]!=x||t[x].ch[1])return;
	t[x].fa=t[y].ch[0]=0;
	pushup(y);
}
int findroot(int u){
	access(u),splay(u);
	while(t[u].ls)u=t[u].ls;
	return u;
}

五.其他技巧

1.查询深度

先将节点

\text{access}

一遍，再

\text{splay}

到根，最后所在实链的

\text{size}

就是该节点在原树上的深度。（根在实链顶端， $x$ 在实链底端，此时根与 $x$ 的距离就是实链的节点数减一，因此 $x$ 的深度就是实链的节点数减一再加一，也就是实链的节点数）

2.查询 LCA

若要求节点

x

，

y

的 LCA ，则先建一条从根到

x

的实链，再建一条从根到

y

的实链，接着将

x

旋转到根，然后会有三种情况：

$x$ 为 $y$ 的祖先，此时 $x$ ， $y$ 的 LCA 为 $x$ ，因此我们判断 $x$ 是否还在根所在的实链上，如果是就直接返回 $x$ 。（若 $x$ 还在这条实链上，则说明 $y$ 在 $\text{access}$ 时访问到 $x$ ，因此 $x$ 就是 $y$ 的祖先）
$y$ 为 $x$ 的祖先，此时 $x$ ， $y$ 的 LCA 为 $x$ ，于是我们直接返回 $x$ 此时的父亲，也就是 $y$ 。
$x$ 和 $y$ 都不为对方的祖先，此时 $x$ 的父亲就是 $x$ ， $y$ 的 LCA。（因为这是 $x$ 在根所在实链上深度最低的祖先）

容易发现，第二、三种情况都是返回

x

此时的父亲，因此将它们合并为一种。

于是原来的三种情况就变为了两种情况：

x

为

y

的祖先和

x

不为

y

的祖先。

代码实现：

CPP

int lca(int x,int y){
	if(x==y)return x;//特判x和y为同一节点 
	access(x);//建一条从根到x的实链
	access(y);//建一条从根到y的实链
	splay(x);//将x旋转为splay树的根
	if(t[x].fa==0)return x;//x为y的祖先
	return t[x].fa;//x不为y的祖先 
}

六.习题

P3690 【模板】动态树（LCT）

这是动态树的模板题，需要把刚才代码中 pushup 操作的加法改成异或。

注意：在连边时要通过 $\text{findroot}$ 操作判断两点是否连通。

P1501 [国家集训队] Tree II

这题在原来翻转标记的基础上增加了加标记和乘标记，需要明确各种标记的下传顺序。

P2173 [ZJOI2012] 网络

这题需要先将图上问题转化成树上问题，它与模板 LCT 的区别在于需要将边权转化为点权，再维护路径信息。

P4299 首都

这道题需要将 LCT 与树的重心结合，通过 LCT 动态维护树的重心，比较考验综合能力。

浅谈LCT

文章操作

动态树 LCT (Link - Cut - Tree)

一、什么是 LCT ？

二、LCT 的原理

1. 建立辅助树

2. $\text{access}(x)$ 操作

3. $\text{reverse}(x)$ 操作

4. $\text{makeroot}(x)$ 操作

5. $\text{split}(x,y)$ 操作

6. $\text{link}(x,y)$ 操作与 $\text{cut}(x,y)$ 操作

7. 信息维护

8. 其他函数

三、时间复杂度

四.程序实现

1.结构体定义

2. $\text{isroot}$ 操作（查找某节点是否为该节点所在 splay 树的根）

3. $\text{pushup}$ 操作（信息上传）

4. $\text{reserve}$ 操作（翻转左右子树）

5. $\text{pushdown}$ 操作（标记下传）

6. $\text{push}$ 操作（标记全部下传）

7. $\text{rotate}$ 操作

8. $\text{splay}$ 操作

9. $\text{access}$ 操作

10. $\text{makeroot}$ 操作

11. $\text{split}$ 操作

12. $\text{link}$ 操作

13. $\text{cut}$ 操作

14. $\text{findroot}$ 操作（查找节点所在树上的根）

所有函数

五.其他技巧

1.查询深度

2.查询 LCA

六.习题

相关推荐

评论

浅谈LCT

文章操作

动态树 LCT (Link - Cut - Tree)

一、什么是 LCT ？

二、LCT 的原理

1. 建立辅助树

2. access(x)\text{access}(x)access(x) 操作

3. reverse(x)\text{reverse}(x)reverse(x) 操作

4. makeroot(x)\text{makeroot}(x)makeroot(x) 操作

5. split(x,y)\text{split}(x,y)split(x,y) 操作

6. link(x,y)\text{link}(x,y)link(x,y) 操作与 cut(x,y)\text{cut}(x,y)cut(x,y) 操作

7. 信息维护

8. 其他函数

三、时间复杂度

四.程序实现

1.结构体定义

2.isroot\text{isroot}isroot 操作（查找某节点是否为该节点所在 splay 树的根）

3.pushup\text{pushup}pushup 操作（信息上传）

4.reserve\text{reserve}reserve 操作（翻转左右子树）

5.pushdown\text{pushdown}pushdown 操作（标记下传）

6.push\text{push}push 操作（标记全部下传）

7.rotate\text{rotate}rotate 操作

8.splay\text{splay}splay 操作

9.access\text{access}access 操作

10.makeroot\text{makeroot}makeroot 操作

11.split\text{split}split 操作

12.link\text{link}link 操作

13.cut\text{cut}cut 操作

14.findroot\text{findroot}findroot 操作（查找节点所在树上的根）

所有函数

五.其他技巧

1.查询深度

2.查询 LCA

六.习题

相关推荐

评论

2. $\text{access}(x)$ 操作

3. $\text{reverse}(x)$ 操作

4. $\text{makeroot}(x)$ 操作

5. $\text{split}(x,y)$ 操作

6. $\text{link}(x,y)$ 操作与 $\text{cut}(x,y)$ 操作

2. $\text{isroot}$ 操作（查找某节点是否为该节点所在 splay 树的根）

3. $\text{pushup}$ 操作（信息上传）

4. $\text{reserve}$ 操作（翻转左右子树）

5. $\text{pushdown}$ 操作（标记下传）

6. $\text{push}$ 操作（标记全部下传）

7. $\text{rotate}$ 操作

8. $\text{splay}$ 操作

9. $\text{access}$ 操作

10. $\text{makeroot}$ 操作

11. $\text{split}$ 操作

12. $\text{link}$ 操作

13. $\text{cut}$ 操作

14. $\text{findroot}$ 操作（查找节点所在树上的根）