Link Cut Tree.

Presentation on theme: "Link Cut Tree."— Presentation transcript:

1 Link Cut Tree

2 Link-Cut-Tree是什么？ 一种数据结构！ 能够维护一个带权的森林。 支持link（加边）、cut（删边）操作，动态的森林！
所有操作均摊复杂度O(log (N))！ 在网络优化中的用途十分广泛！

3 Link-Cut-Tree的基本操作 Parent(v) 返回v的父亲节点。​ Root(v) 返回包含节点v的树的根。​
Link(v,w)将以v为根的树连接到节点w上。​ Cut(x,y)从树中删除边(x,y)，分为两棵树。​ Evert(v) 将v设为根，并将v到Root(v)上所有边反向。​

4 Link-Cut Tree 如何对树进行操作？​
并不直接对整棵树进行操作。​ 将树中的边分成实虚两种。​ 从每个顶点出发，最多只有1条实边连向它的子节点。​ 那么实边可以组成若干条路径，我们采用splay来维护这些路径。 剩下的边都是虚边。​ 有一种核心操作Access(v)，来对虚、实边进行维护。

5 Splay维护路径？ 首先我们知道splay可以维护序列。 例如： 在LCT中，BST的顺序按照到根的距离从小到大排列。 5 2 4
可以按照顺序组成一棵Binary Search Tree。 上面的序列组成的图（可能的一种）： 这么一个BST，中序遍历就是原序列。 那么这个序列也可以看成是路径： 10->2->5->4->8->7->6->1->3->9 在LCT中，BST的顺序按照到根的距离从小到大排列。 3 10 7 9 8 6 1

6 Access(v)？ Access(v)的作用就是：将Root到v这条路径上的边设置为实边。
先了解Access(v)的子过程Splice(p, Parent(p))

7 Splice(p, Parent(p)=v)

8 过程是这样的： 首先，要满足每个点向下连接的实边只有一条。 那么先切断v和q的实边连接 再连接好v和p 那么这一次切换就完成了
那么新的序列就是：r->v->p->…

9 Splice(p, parent) Splay(parent);
RightChild(parent) = p; //RightChild是parent在splay中的右孩子，这里 保证是它的实孩子

10 Access(v)

11 Access(v) 不断调用Splice，直到根为止
for (x = v , y = NULL ; x ; x = Parent(x)) { Splice(y, x);//注意，第一次执行时，y=NULL，表示直接切除x向下的实边 y = x; }

12 基本操作的实现 Link(x,y): Evert(x); Splay(x); Parent(x)=y; Cut(x,y):
if(parent(x) == y) //y is father swap(x, y); //now x is father Access(y); splay(x); tree[x].ch[1] = tree[y].fa = NULL; update(x); //更新x的信息，optional Evert(y); //optional Evert(v): Access(v); Splay(v); MarkReverse(v); Root(v): Access(v); Splay(v); return FindMin(v); Parent(v): Access(v); return FindPrevious(v); MarkReverse(v)表示将v所在的splay的顺序颠倒，详细实现这里略过。 FindMin(v)表示找到v所在的splay的最小值，即对应路径的第一个节点。

13 如何查询一条链？ 假设目标链的起止点为(x,y) 那么： Query(x,y):
Evert(x); Access(y); return node[y].ALL_information; ALL_information表示以y为根的splay tree的所有节点的information的和。