Link Cut Tree

简介

  1. Link/Cut Tree 是一种数据结构,我们用它来解决动态树问题
  2. Link/Cut Tree 又称 Link-Cut Tree,简称 LCT,但它不叫动态树,动态树是指一类问题。
  3. Splay Tree 是 LCT 的基础,但是 LCT 用的 Splay Tree 和普通的 Splay 在细节处不太一样(进行了一些扩展)。
  4. 这是一个和 Splay 一样只需要写几 (yi) 个 (dui) 核心函数就能实现一切的数据结构。

问题引入

  • 维护一棵树,支持如下操作。
  • 修改两点间路径权值。
  • 查询两点间路径权值和。
  • 修改某点子树权值。
  • 查询某点子树权值和。 唔,看上去是一道树剖模版题。

那么我们加一个操作

  • 断开并连接一些边,保证仍是一棵树。

要求在线求出上面的答案。

——动态树问题的解决方法:Link/Cut Tree!

动态树问题

  • 维护一个森林, 支持删除某条边,加入某条边,并保证加边,删边之后仍是森林。我们要维护这个森林的一些信息。
  • 一般的操作有两点连通性,两点路径权值和,连接两点和切断某条边、修改信息等。

从 LCT 的角度回顾一下树链剖分

  • 对整棵树按子树大小进行剖分,并重新标号。
  • 我们发现重新标号之后,在树上形成了一些以链为单位的连续区间,并且可以用线段树进行区间操作。

转向动态树问题

  • 我们发现我们刚刚讲的树剖是以子树大小作为划分条件。
  • 那我们能不能重定义一种剖分,使它更适应我们的动态树问题呢?
  • 考虑动态树问题需要什么链。
  • 由于动态维护一个森林,显然我们希望这个链是我们指定的链,以便利用来求解。

实链剖分

  • 对于一个点连向它所有儿子的边 , 我们自己选择一条边进行剖分,我们称被选择的边为实边,其他边则为虚边。
  • 对于实边,我们称它所连接的儿子为实儿子。
  • 对于一条由实边组成的链,我们同样称之为实链。
  • 请记住我们选择实链剖分的最重要的原因:它是我们选择的,灵活且可变。
  • 正是它的这种灵活可变性,我们采用 Splay Tree 来维护这些实链。

LCT!

  • 我们可以简单的把 LCT 理解成用一些 Splay 来维护动态的树链剖分,以期实现动态树上的区间操作。
  • 对于每条实链,我们建一个 Splay 来维护整个链区间的信息。
  • 接下来,我们来学习 LCT 的具体结构。

辅助树

  • 我们先来看一看辅助树的一些性质,再通过一张图实际了解一下辅助树的具体结构。
  • 在本文里,你可以认为一些 Splay 构成了一个辅助树,每棵辅助树维护的是一棵树,一些辅助树构成了 LCT,其维护的是整个森林。

  • 辅助树由多棵 Splay 组成,每棵 Splay 维护原树中的一条路径,且中序遍历这棵 Splay 得到的点序列,从前到后对应原树“从上到下”的一条路径。

  • 原树每个节点与辅助树的 Splay 节点一一对应。
  • 辅助树的各棵 Splay 之间并不是独立的。每棵 Splay 的根节点的父亲节点本应是空,但在 LCT 中每棵 Splay 的根节点的父亲节点指向原树中 这条链 的父亲节点(即链最顶端的点的父亲节点)。这类父亲链接与通常 Splay 的父亲链接区别在于儿子认父亲,而父亲不认儿子,对应原树的一条 虚边。因此,每个连通块恰好有一个点的父亲节点为空。
  • 由于辅助树的以上性质,我们维护任何操作都不需要维护原树,辅助树可以在任何情况下拿出一个唯一的原树,我们只需要维护辅助树即可。(本句来源自 @PoPoQQQ 大爷的 PPT)

  • 现在我们有一棵原树,如图。

  • 加粗边是实边,虚线边是虚边。

tree

  • 由刚刚的定义,辅助树的结构如下

auxtree

考虑原树和辅助树的结构关系

  • 原树中的实链 : 在辅助树中节点都在一棵 Splay 中。
  • 原树中的虚链 : 在辅助树中,子节点所在 Splay 的 Father 指向父节点,但是父节点的两个儿子都不指向子节点。
  • 注意:原树的根不等于辅助树的根。
  • 原树的 Father 指向不等于辅助树的 Father 指向。
  • 辅助树是可以在满足辅助树、Splay 的性质下任意换根的。
  • 虚实链变换可以轻松在辅助树上完成,这也就是实现了动态维护树链剖分。

接下来要用到的变量声明

  • ch[N][2] 左右儿子
  • f[N] 父亲指向
  • sum[N] 路径权值和
  • val[N] 点权
  • tag[N] 翻转标记
  • laz[N] 权值标记
  • siz[N] 辅助树上子树大小
  • Other_Vars

函数声明

一般数据结构函数(字面意思)

  1. PushUp(x)
  2. PushDown(x)

Splay 系函数(不会多做解释)

  1. Get(x) 获取 x 是父亲的哪个儿子。
  2. Splay(x) 通过和 Rotate 操作联动实现把 x 旋转到当前 Splay 的根
  3. Rotate(x) x 向上旋转一层的操作。

新操作

  1. Access(x) 把从根到 x 的所有点放在一条实链里,使根到 x 成为一条实路径,并且在同一棵 Splay 里。只有此操作是必须实现的,其他操作视题目而实现。
  2. IsRoot(x) 判断 x 是否是所在树的根。
  3. Update(x)Access 操作之后,递归地从上到下 Pushdown 更新信息。
  4. MakeRoot(x) 使 x 点成为其所在树的根。
  5. Link(x, y) x, y