Link-cut tree

数学模型
• 可以将其抽象为一棵树，若i会弹到节点j， 那么i的父亲为j，若弹飞则i的父亲为根。那 么这道题就是询问某个点树的深度，以及 支持将树中某个子树切除，并连接到另一 个节点。 • 用link-cut-tree解决！
Link-cut tree
• 树链：是树的一条路径，但只会从上往下 （即深度依次加1）。
[ZJOI2008]树的统计Count
• 这个题是要维护树上一条路径的信息， Access(v)只是可以维护出从v到根的信息， 那么我们可以将其改造一下，对与u到v的 路径，我们可以先Access(v)，然后Access(u) 的时候，如果u的父亲和v在同一个splay中 了，那就停止，这样u的父亲就是u和v的 LCA，这样我们会有两个splay，其中路径上 的点就是u所在splay和LCA以及他的右子树。
Βιβλιοθήκη Baidu
Link-cut Tree
• 最大的优点就是功能强大，比方说可以求 LCA，可以当并查集用，主要还可以动态的 维护森林上的各种操作。还有一个特点就 是比较好写，splay本身不算难写，核心操 作access只有区区10余行。还有一个缺点就 是慢，由于access是logn的，于是所有操作 都是logn的，但是由于splay的巨大常数，让 他比其他数据结构的效率要低一些。
Link-cut Tree
Access(v)前
Access(v)后
Link-cut Tree
• Access(v)：先Splay(v)，并砍掉v的右孩子(这 是用来断开比v深的树链)。设w为v的父亲， 那么Splay(w), 将w的右儿子换成v，这样w和 v就连在一起了，此时w为树链的根，那么 令v=w, w = w->father。继续此过程，直到v 没有父亲为止。
[ZJOI2008]树的统计Count
Access(v)
Access(u)
Access的一种实现方式
• void access(Node* x, bool flag = false) { Node *p = x, *q = nil; while (p != nil) { splay(p); if (flag && p->f == nil) break; //如果flag是true，那就早一点停下来。 p->rc->isRoot = true; p->rc = q; q->isRoot = false; p->update(); q = p; p = p->f; } }
[ZJOI2008]树的统计Count
• 一棵树上有n个节点，编号分别为1到n，每 个节点都有一个权值w。 我们将以下面的形 式来要求你对这棵树完成一些操作 I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节 点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节 点的权值和
Link-cut tree
[Hnoi2010]Bounce
• 某天，Lostmonkey发明了一种超级弹力装置， 为了在他的绵羊朋友面前显摆，他邀请小绵羊 一起玩个游戏。游戏一开始，Lostmonkey在地 上沿着一条直线摆上n个装置，每个装置设定 初始弹力系数ki，当绵羊达到第i个装置时，它 会往后弹ki步，达到第i+ki个装置，若不存在第 i+ki个装置，则绵羊被弹飞。绵羊想知道当它 从第i个装置起步时，被弹几次后会被弹飞。 为了使得游戏更有趣，Lostmonkey可以修改某 个弹力装置的弹力系数，任何时候弹力系数均 为正整数。
Link-cut Tree
• Find Root(v)：先Access(v)，此splay的最左边 即为根。 • cut(v)：splay(v)，然后用v左儿子代替v。 • Join(v, w)：Access(v)，然后令v的父亲为w,在 Access(v)（这是为了更新数据，比方说size 之类的）。
• 右图的树有4个树链 特殊的，一个点我 们也认为是一个树 链
Link-cut Tree
• 一个森林是由多个树构成，一棵树可以看 做是由多个树链构成，每个树链会有一个 父亲。 • Link-cut Tree就可以认为是这样的一个森林， 其中每个树链由一棵splay来维护。在这里 我们认为如果节点v是他所在的树链的splay 的根，那么他的父亲就是这个树链的父亲 （实际树中深度最小的节点的父亲），否 则就是splay中的父亲。
• 想看更专业的东西，请参考杨哲的《QTREE 解法的一些研究》
Link-cut Tree
• 支持的操作： • Access(v)：所有操作的基础，如果调用了 Access(v)，那么节点v到根就会成为一个新 的树链。 • Find Root(v)：找到v所在树的根。 • Cut(v)：将v及其子树与原树断开。 • Join(v, w)：将v所在树连接到另一棵树的节 点w上。