原文连接 (YSP dalao%%%%%):http://www.cnblogs.com/Robert-Yuan/p/5122784.html
本文是蒟蒻 XZY 转自学长 YSP 的博客的!
其实讲的是动态树中的一种——lct(link cut tree)
蒟蒻 XZY 再推荐一些博客:
http://blog.csdn.net/jeremygjy/article/details/51078087
http://www.cnblogs.com/BLADEVIL/p/3510997.html

再提供一个杨哲的论文——《QTREE 解法的一些研究》:
QTREE 解法的一些研究

动态树入门

好文链接,写的比较好懂…. 只是这人有点奇怪…..:http://www.aiuxian.com/article/p-2284697.html

代码有的句子很诡异的感觉…

例如说:"由于 l 变成了一棵树的根,所以 splay 它"….

好鬼啊!…. 不过写的真的很好懂的样子….

同样推荐的有:

  <高级数据结构>

  <2006-陈首元-维护森林连通性_动态树>

  <2007-袁昕颢-动态树及其应用>[感觉这个格外高神一些…. 有的还是看不懂….]

<LCT 游记-Robert>

[初次见面]

我来到一片广袤无垠的森林,这里居然只有一个种群——大约 10^5 片点.
森林里当然有很多很多树了,但是刚开始树上一般只有一个点,可是树之间抱着互利共生 [其实它们是同一种类,不能叫互利共生] 的思想,通常会联合起来变成一棵大树,变成大树就可以 A 了 BRUCE 了 (雾)

[粗略看了看树]

但是你如果仔细观察的话,树上的叶子之间有两种关系,一个是铁哥们-实边,一个是普通朋友-虚边.当然很多时候友谊关系会变化 [为了 oier 的利益变化,奉献精神啊有木有].
不管怎样,实边总是会构成一条条深度连续而不相同的链 [在整个树的形态中由下而上,没有弯折],而且没有一个点会在两条实链中

[oier 的出现]

现在这些点们想帮助 oier 解决问题,oier 说:"我希望你们内部团结".
于是一群铁哥们之间 [一条实链] 就形成了一个名叫 splay 朋友圈的组织,一颗树被分成了很多个 splay.
oier 又说:"我还希望你们的一棵树上也要团结"
于是 splay 之间用虚边连接 [每个朋友圈都有人和在这个朋友圈以上的朋友圈的最矮的人是普通朋友]
必要的时候会让这些连接的虚边变成实边,从而完成 oier 的任务

[splay 朋友圈的内部构造]

有了 splay 这些铁哥们之间就可以在这个 splay 朋友圈里面旋转旋转了.
不过除了特殊情况,它们之间的相对位置是不会变的
"站在我左边的是比我高的,右边是比我矮的."-Zero 说.
朋友圈里等级制度还是有的 [虽然会发生旋转]
只有朋友圈的老大 [身份老大,身高不一定哦] 才知道与另外一个更高层的朋友圈的普通朋友是谁.
其它的人只知道自己在朋友圈里的联系人.

[oier 的任务]

[Mission 1 – Splay]

x 需要通过旋转成为所在朋友圈的老大.
zig(x),zag(x)… 完成任务.

[Mission 2 – Access]

当我们需要构建一条情报通道从初始点 x 到树顶部时 [那里有无线电台,可以让所有的点都与它产生联系]
就需要一种变换 Access().

提醒:这是在原树中,所以必须时刻假想朋友圈在原树上的刻画 [一条链]

首先将 x 变成自己朋友圈的老大,这时他有权有势了,于是先踢掉了比自己矮的铁哥们 [splay 断右子树,在原树中就是断开 x 下面的链]
而且 x 成为了老大,于是联系上的其它朋友圈里的联系人 y.
"头儿让我传信息"
"那我们是铁哥们了"
这时 x 融入了上层朋友圈 [不过他不是老大了],y 不一定是老大,于是它先需要变成朋友圈老大 [这时右子树不一定为空,所以还需要将右子树独立出来,rt=true],然后将 x 纳入它的右子树中
然后 y 给它现在知道的联系人 z 打电话
"头儿让我传消息"
"你来吧"
这时 y 融入了更上层朋友圈 [他也不是老大了],z 先变成朋友圈老大,安顿好比它矮的,然后将 y 纳入比它矮的铁哥们中
…. 循环了
终于它找到了根节点 [这个人所在的朋友圈没有上级,而且是最高的点]

"终于找到组织了!"x 说.
完成任务.

[Mission 3 – make_rt]

我们需要任命 x 为新的根节点
首先构造 x 到根节点的沟通路径,但是 x 要做新的根节点,他要成为最高的 [原本是这个朋友圈里最矮的哦…]
那么这条路上的所有节点都应该在朋友圈里反着站.[树边反着指]
就是将 x 成为老大后,进行翻转操作.
完成任务.

[Mission 4 – Link]

现在两棵树里的 u,v 想要认识,
"我们要创造条件啊"Zero 说.
于是 u 成为了所在树的新根节点,然后顺理成章的向上一指,成为了 v 的新的一棵子树 [目前还只是普通朋友].
完成任务.

[Mission 5 – Cut]

u,v 两人闹不和了… 要解除关系
我们不能违逆啊…
首先让 u 当上树根,这样另一人 v 一定在 u 的某棵子树 [因为他们俩认识] 下.
在打通这个人与树根的关系 [分别前最后一次成为铁哥们…]
然后 v 当上它们之间的朋友圈老大,跟 u 交代完后,扔下 u 成了孤零零的朋友圈老大…[当然 u 也是原树的根节点]
自己带着跟随自己的兄弟们离开了树… 黄昏里萧瑟的背影拉的老长老长…
完成任务.

[离去]

这里的点生物真是机智又可爱啊… 但是我还是要离去了…OI 大陆还有很多的东西在等着我哦…

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注