介绍

实质上是维护森林, 支持了许多动态操作:

  • 查询, 修改链上的信息(最值, 总和等)
  • 动态添删边
  • 动态维护连通性等功能

而它依靠的是虚实边的动态维护!


所维护的

考虑每个联通块(更准确说是一颗森林中树)的维护:

其中的每条实链, 均用splay来维护, 且splay所形成的树型结构称为辅助树

它应具有以下性质

  1. splay 维护的是一条原树上的深度严格递增的路径, 即中序遍历 splay得到的dfs序满足在原树上深度递增

  2. 每个节点包含且仅包含于一个splay

  3. 边分为实边和虚边, 实边包含在splay中, 而虚边总由一棵 splay指向另一个节点(指向该Splay中中序遍历最靠前的点在原树中的父亲)

    根据性质2: 在原树中存在多个子节点时, 只能挑选一个节点的连边作为实边;

    那么为了保持树的形状, 要让到其它儿子(v)的边变为虚边, 由对应儿子所属的splay的根节点的父亲为该点(u),而从u并不能直接访问v(认父不认子)

example :

  • 原树(即森林中的某棵树)
  • 辅助树(每个绿框表示一颗splay)

各种操作

access


也算是\text{lct}中最重要的操作了吧…

它的作用在于打通指定节点到跟的实链, 使得一条中序遍历以根开始且以指定点结束的splay出现

研读上一句话, 发现就是原树上u-root的路径变成实链, 而与其相邻的实边都要变成虚边!

那…具体怎么实现 :confused:

  • 若我们在原树上的(u,v) 是一条虚边, u深度较小, 那么u 所在的splay中它是最深的

  • 同样的, v是它splay中深度最小的.

先将u rotate至根节点, 如果它所在的实链还未结束, 那么其他链上节点都在辅助树中该点的右侧, 断开即可…

再将v rotate至根节点, 显然fa_v=u那么我们只要往上连就好了!

void access(int x){
    int t = 0;
    while (x) {
        splay(x), son[x][1] = t;
        t = x, x = fa[x];
    }
}

revers


换根操作

函数的作用在于将x变成所在树的根

void rever(int x){
    access(x), splay(x), rev[x] ^= 1;
}

比较好理解, 就是将x先与根的splay打通, 在转到根(注意这时候 x是没有右子树的)

由于换根相当于是深度翻转, 那么打一个tag就好了

link


意在连接x, y 的边, 如果数据合法, 只要这样:

void link(int x, int y){
    rever(x), fa[x] = y;
}

意在说明将x作为辅助树的根, 就取消了father的影响, 那么只要向y连接一条虚边就好了, 表示连通的两颗树, 且对应的虚边(x, y)也是原树的边!

cut


void cut(int x, int y){
    rever(x), access(y), splay(y), fa[x] = son[y][0] = 0;
}
  • rever(x): 将 x 变成该连通块的根
  • access(y): 打通从 y 到该连通块根 x 的一条路径
  • splay(y): 将 y 已到辅助树根位置
  • 这时,由于 xy 在同一连通块且有直接连边,又因为
    x 的深度比 y 小,所以在辅助树中 x 必然是 y 的左子节点, 那么直接断开就好了

总结

并不需要将所有操作思考的如此细节:joy:

  • 我们类似的只要考虑每个splay维护的是一条实链

  • splay的根的fa意在于是原树的连边(即splay中深度最小的边连向fa)就好了! ( 这是性质

比如access 就联想到原节点到钦定树根的路径变成实边就好了, 对, 就好了!

这样只要联想虚实边就好了!

妙(du)妙(liu) 啊 :tada:

其他非基本操作

  1. lca

    \text{access(u)} 那么(u,root)的路径都变成了实链.

    那么在\text{access(v)} 的时候就相当于把(lca_{u,v}, root)的边当做实链, 参考\text{access}操作的时候会有一个向上跳父亲的操作, 然后将它splay成根, 那么最后操作的点就是答案了!

    int access(int x, int las = 0) {
           for(; x; ) {
               splay(x), rs(x) = las;
               las = x, x = fa(x);
           } return las;
       }
    
  2. 维护链

  • 点权类型: 就是splay(或者什么线段树)的basic操作吧

  • 边权类型: 由于lct不好维护边权, 那么我们可以添加辅助点k, 使得link(u,k) + link(v,k)就变成维护点权的题目了!

  1. 维护子树信息

    参考博客: neither_nor’s Blog

    ![](https://img-blog.csdn.net/20170405195510546)

  • 定义辅助树上的父子关系(点x的儿子)
    为有虚边指向x的点或者在splay中是x的儿子的点

    例如上图中,4的实儿子有2,虚儿子有7,实子树(2)包含2,5,6,8,虚子树(7) 包含7.

    • 考虑维护

      如果对x进行access操作,那么它的总虚子树信息将包含且仅包含原树中的子树(除了自己以外)的所有点,将这个信息与x自己的信息合并,就得到了他在原树中的子树信息. 所以考虑维护它

      • 发现需要同时维护点的虚子树信息lct子树信息来达到维护的目的.
      • 那么虚子树改变的情况当且仅当 \text{access or link} 操作

      access

      会有更换路径上某些节点的右儿子操作

      • 只要把x原来的右儿子的LCT子树信息加入x的虚子树信息,把x的新的右儿子的LCT子树信息从x的虚子树信息中减去

      link

      在进行link操作时,我们会先把点x换根,然后连一条xy的虚边,这时我们发现不仅y的虚子树信息需要加入xLCT子树信息,y的所有祖先的LCT子树信息也需要更改(二者同时需要维护)

      • y也换根(或者直接access 并且 splay 也可以)
      • 然后只会对y的两个信息产生影响.

参考文献

  1. flashhu’s lct Blog

  2. zhouzhendong’s lct Blog