LCT 学习笔记

Link-Cut-Tree 是一种用来解决动态树问题的数据结构，自由度极高。

所谓动态树，就是指支持动态删边，加边，但保证操作后仍是一棵树。

由于这棵树本身是没有什么很好的方法动态维护的，所以考虑用一些本身支持动态且可以与对应回原树的数据结构来维护。注意是单射，一棵树可能对应多个合法的辅助树，这也是自由度高的一个原因。

于是就诞生了 $LCT$ ，它是一个 $Splay$ 森林。每一颗 $Splay$ 的中序遍历对应原树上的一条链。除此以外，自由度非常的高。每颗 $Splay$ 之间以虚边连接，即所谓的认父不认子，只将 $fa_x$ 指向 $y$ 而不将 $ls_y , rs_y$ 指向 $x$ 。这么做是由于会产生链的变化以及辅助树本身的变化，不能彻底与原树上父亲节点断绝联系，但必须保证 $Splay$ 之间互不干扰。

具体实现：

每颗 $Splay$ 需要维护的信息：

$ch_{0/1}$ 分别表示左右子节点。
$fa$ 表示当前节点的父亲节点。
$rev$ 子树翻转标记。
$val$ 表示当前节点的权值。
$sz/sum/max/min\cdots$ 表示当前子树的各类权值。

要实现的操作：

首先是对 $Splay$ 的一些引用和拓展。

$isroot$ 这个操作是由于认父不认子，所以需要对 $Splay$ 根进行的特殊判断。
$pushup$ 正常的 $Splay$ 操作
$reverse$ 在 $Splay$ 上翻转子树，同时打上翻转标记。
$spread$ 下传操作，类似线段树。
$rotate$ , $splay$ 均为正常的 $Splay$ 操作。

接下来的几个就是新的操作了。

$access$ 把 $x$ 到根的路径全部变成实链。

实现方法：从 $x$ 一直跳 $fa$ 跳到原树根，每跳一次将当前节点旋转到当前 $Splay$ 的根。并将上一次的节点接到当前节点的右子节点。并 $pushup$ 信息。
$makeroot$ 把当前节点变成原树的根。

实现方法：先在辅助树上把 $x$ $access$ 一下，然后将 $x$ $splay$ 到根，最后翻转 $x$ 的子树（因为性质中序遍历对应原树链）。
$findroot$ 找到当前原树的根节点。

实现方法：同样先将 $x$ $access$ 接 $splay$ ，然后只需要一直跳左子节点即可。

接下来是两点之间的操作。

$split(x, y)$ 把 $x, y$ 之间的链单拎出来变成实链，断开 $x\to y$ 与其他点之间的实链。

实现方法：先把 $x$ 变成根，然后 $access$ $y$ ，拎出来链，最后 $splay$ $x$ 或 $y$ 来达到将链上的信息传到某端点。
$link(x, y)$ 把 $x, y$ 在原树上连一条边。仍然是先将 $x$ 变成根，然后 $findroot(y)$ 来检查一下之前有没有连边（数据不保证合法的情况下，防止出环），没有的话直接将 $fa(x)$ 设为 $y$ 。
$cut(x, y)$ 断掉 $x, y$ 在原树上的边。如果没有保证数据合法，就要先将 $x$ 变成根，然后 $access$ $y$ 并进行一系列的检查，保证 fa(y) == x && findroot(y) && !ls(y) 都符合的情况下，将 $x$ 的右儿子和 $fa_y$ 同时断掉。保证合法的话直接 $split$ ，再断掉即可。

总之， $LCT$ 所做的就是利用极高的灵活性把树特殊化，来达到快速求值的目的，如链之间的操作直接把某端点变成根。

代码实现：

// LCT 学习笔记 || LCT 具体实现
struct node {
  int rev, fa, ch[2];
  #define r(x) Sp[x].rev
  #define fa(x) Sp[x].fa
  #define ls(x) Sp[x].ch[0]
  #define rs(x) Sp[x].ch[1]
  #define ch(x, y) Sp[x].ch[y]
} Sp[Maxn];

bool isroot(int x) {return ls(fa(x)) != x && rs(fa(x)) != x;}
void reverse(int x) {swap(ls(x), rs(x)); r(x) ^= 1;}
void spread(int x) {
  if (r(x)) {
    if (ls(x)) reverse(ls(x));
    if (rs(x)) reverse(rs(x));
    r(x) = 0;
  }
}

void rotate(int x) {
  int y = fa(x), z = fa(y), c = rs(y) == x, w = ch(x, !c);
  if (!isroot(y)) ch(z, rs(z) == y) = x;
  ch(x, !c) = y, ch(y, c) = w;
  if (w) fa(w) = y;
  fa(y) = x, fa(x) = z;
}

void splay(int x) {
  static int stc[Maxn], top, y, z;
  top = 0, y = x, stc[++top] = y;
  while (!isroot(y)) stc[++top] = y = fa(y);
  while (top) spread(stc[top--]);
  while (!isroot(x)) {
    y = fa(x), z = fa(y);
    if (!isroot(y)) rotate((rs(y) == x) ^ (rs(z) == y) ? x : y);
    rotate(x);
  }
}

void access(int x) {for (int y = 0; x; x = fa(y = x)) splay(x), rs(x) = y;}
void makeroot(int x) {access(x), splay(x), reverse(x);}
int findroot(int x) {
  access(x), splay(x);
  while (ls(x)) spread(ls(x)), x = ls(x);
  splay(x); return x;
}

void split(int x, int y) {makeroot(x), access(y), splay(y);}
void link(int x, int y) {makeroot(x); if (findroot(y) != x) fa(x) = y;}
void cut(int x, int y) {
  makeroot(x);
  if (findroot(y) != x || fa(y) != x || ls(y)) return;
  fa(y) = rs(x) = 0;
}

一些小的 $Trick$ || 应用：

$LCT$ 不能维护边权，所以对于每条边，要新建一个节点，连在原树上连个点之间，并将这个点的权值赋成原树上的边权。
$LCT$ 可以通过维护第二个权值来单独维护虚子树信息。只需要在 $access, link, cut$ 等涉及实虚边转化的函数中进行修改即可。

本文作者：CloudySky
写作时间： 2022-02-18
最后更新时间： 2022-02-27
遵循协议： BY-NC-SA

CloudySky || AFO

永远相信美好的事情即将发生。

LCT 学习笔记