AC. 梦想

frank_c1

动态树问题小结

发布于2016年02月28日 | 暂无评论 | 3,328阅读 | LCT

先膜一膜杨哲神犇关于QTREE解法研究的论文。

在信息学中,树是一个神奇的物种。树能以静止的状态存在,也可以时不时变化一下点的权值、边的权值,有时也可以动起来,旋转一下、重构一下…… 玩法很多。现在又有新花样了,我们需要维护一棵树的形态,这棵树有时可能会断掉某条边,变成两棵子树;有时两棵子树某两点间连上一条边,就合并成一棵树。同时要求维护树的一些信息,比如两点间路径点权的最大值,两点间路径长度等等。

于是,一种新的数据结构——Link-Cut Tree应运而生。这种传奇的数据结构是伸展树的发明者Tarjan大师提出的。带着崇敬的心态膜完LCT后,我发现这种简洁高效的数据结构真的是颠覆了我的认知,于是来总结一下。

回顾树链剖分,我们用线段树来维护结点的相关信息。但在这里,线段树显然不够灵活了,于是我们用更灵活的splay来维护树的形态。像树链剖分一样,树上剖成若干条链,每条链用一个Auxiliary Tree(实质是splay)维护。Auxiliary Tree以结点在树中的深度为关键字(从小到大)维护链的形态。每棵Auxiliary Tree的根节点的父亲指向它所表示的链的顶端节点在树中的父结点,其它结点的父亲指向它在Auxiliary Tree中的父结点,而不是在实际树中的父亲。

2016022801

如图所示,图中黑色部分为实际树的形态,蓝色部分为我们维护的若干棵Auxiliary Tree(注意,因为Auxiliary Tree实际上是splay,是可以旋转的,所以此处的状态仅为一种可能的情况)。黑色粗边相连的是一条链,同一条链中的结点应在同一棵Auxiliary Tree里面;蓝色虚线是Auxiliary Tree之间的链接。这样的设计,是可以体现出实际树的形态的。

Link-Cut Tree的几个常用操作:

访问:access(x)

access操作是LCT的核心操作,几乎是所有操作的重要组成部分。

2016022802

还是以前面的树为例。上图中左树是原来的状态,右树是access(3)之后的状态。可以看到,在访问某结点后,该结点到根节点的路径就好像“打通”了。具体来说,对于某结点x,在access(x)后,x结点所在Auxiliary Tree中键值最大的结点是x,键值最小的结点是根。这就方便我们对这条路径施加某些操作。

具体过程:先将x旋转到其所在Auxiliary Tree的根,然后断开根与右子树的连接,使其成为一条独立的链;接着走到当前链的顶端节点在树中的父结点,将结点旋转到根,如果该节点的右子树不是空树,则将右子树断开,接上原来包含x的Auxiliary Tree;如此迭代,直到根节点也被x所在的Auxiliary Tree包含。

寻根:findroot(x)

寻找x所在树的根节点。先access(x),然后将x旋转到根。注意到x所在的Auxiliary Tree键值最小的点即是根,只要在树中一直往左走即可。

换根:makeroot(x)

使x成为其所在树的根节点。先access(x),考虑将x所在的Auxiliary Tree整体翻转,那么x就成为键值最小的结点,达到了换根的目的。

连接:link(u,v)

在结点u,v之间连一条边,保证操作完后依然是一棵树。先makeroot(v),然后将v所在Auxiliary Tree的父亲设为u,注意最后还要access(v)完成信息的更新。

断开:cut(u,v)

将结点u,v之间原来存在的边删去。先makeroot(u),再access(v),将v旋转到根。断开v与v的左子树(即u)的连接,更新一下信息,u和v就真正地分离了。

模板:splay

最后附上相关宏定义和LCT所用splay的模板: