文档介绍：该【算法合集之《维护森林连通性-动态树》】是由【165456465】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【算法合集之《维护森林连通性-动态树》】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。维护森林连通性——动态树
PLEASE ENTER YOUR TITLE HERE
华东师大二附中
陈首元
维护一个森林
01
支持边的插入与删除
02
支持树的合并与分离
03
支持寻找路径上费用最小的边
04
所有操作的均摊复杂度为O(logN)
05
动态树
2
3
4
5
6
7
8
1
10
20
-20
0
30
-5
-5
Root(1,2,3,4,5,6,7,8)=1
MinCost(6)=10
Update(7,10)
5
40
Evert(6)
新树根
Cut(4)
Root(7,8)=4
Link(3,4,10)
Evert(v)使v成为新的根，并将v到原树根上的边反向
Cut(v)删除v与其父节点连接的边
Link(v,w,x)将以v为根的树连接到节点root(w)上，（v,w）的费用为x
Update(v,x)使v到树根路径上的边的费用+x
MinCost(v) 返回v到根路径上费用最小的边
Root(v) 返回包含节点v的树的根
动态树的基本操作
将树中的边分为实边、虚边两种，每个节点最多向其子节点连出一条实边
将树划分为一些完全由实边组成的路径，只对这些路径进行操作
01
02
操作的实现
头
尾
一条路径
路径的基本操作
Path(v)：返回包含v的路径（每个路径有一个标志）
Head(p),Tail(p)：返回首节点、尾节点
Pmincost(p)：返回p中费用最小的边
Pupdate(p,x:real)：将p中每条边的费用+x
Reverse(p)：将p中的每条边反向
Concatenate(p,q,x) ：添加边(tail(p),head(q)）费用为x，将路径p,q合并
Split(v)：将v从路径中删除并把路径分为两部分
Splice
01
Splice(p) ：将路径p向更靠近根的方向增长
实现方法：把虚边(tail(P),Parent(p)) 变为实边，为了维护实边的性质，将原来从Parent(P)中连出的边设为虚边
02
Expose
1
Expose(v)：将从v到树根路径上的所有边设为实边
实现方法：不断调用splice直到根为止
2
有了Expose(v)，就可以实现所有动态树操作了
3
Procedure Link(v,w:vertex;x:real);
01
02
03
04
Begin
Concatenate(path(v),expose(w),x);
End;
Link操作