LCT 学习笔记

2022-11-09 08:00:37

LCT学习笔记

前言

自己定的学习计划看起来完不成了（两天没学东西，全在补题），决定赶快学点东西

于是就学LCT了

简介

Link/Cut Tree是一种数据结构，我们用它解决动态树问题

但是LCT不叫动态树，动态树是指一类问题（那么LCT的中文名是啥啊）

这是⼀个和 Splay ⼀样只需要写几 (yi) 个 (dui) 核心函数就能实现一切的数据结构

动态树问题

维护一个森林，支持删除某条边，加入某条边，并保证加边，删边之后仍是森林。我们要维护这个森林的信息。

一般操作有两点连通性，两点路径权值和，连接两点和切断某条边、修改信息等。

从树链剖分转向动态树问题

普通的树剖以子树大小作为划分条件

然而动态树问题需要什么样的剖分呢？

实链剖分

对于一个点连向儿子的边，我们自行选择一条边进行剖分
称被选择的边为实边，其他边为虚边，实边连向的儿子为实儿子
对于一条实边组成的链，成为实链
采用Splay来维护实链

LCT！

我们把每条实链建一个Splay来维护整个链区间上的信息

辅助树

每⼀个 Splay 维护的是一条路径, 并且在原树中所有节点深度严格递增, 并且, 中序遍历这棵 Splay 得到的点序列列的点深度严格递增。
每个节点包含且仅包含于一棵 Splay 中。
⼀棵 Splay 的根节点的 Father 指向它在辅助树中的父亲结点。但是它父亲结点的 ch 并没有指向这个点的。即父亲不不⼀定认儿子，而儿子一定能找到父亲
我们维护任何操作都不不需要维护原树, 辅助树可以在任何情况下拿出一个唯一的原树, 我们只需要维护辅助树即可。
你可以认为一些 Splay 构成了一个辅助树，每棵辅助树维护的是一棵树，一些辅助树构成了 LCT ，其维护的是整个森林。

Example：

现在有一棵树，其中粗边为实边，虚线边为虚边

那么辅助树的结构如下

原树和辅助树的结构关系

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

变量声明

ch[N][2] 左右⼉子
f[N] ⽗亲指向
sum[N] 路径权值和
val[N] 点权
tag[N] 翻转标记
laz[N] 权值标记

函数声明

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

PushUp(x)
PushDown(x)

Splay 系函数

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

新操作

IsRoot(x) 判断当前节点是否是所在 Splay 的根
Access(x) 把从根到当前节点的所有点放在⼀条实链里, 使根到它成为一条实路径, 并且在同一棵 Splay 里里。
Update(x) 在 Access 操作之后, 递归的从上到下 Pushdown 更新信息。
MakeRoot(x) 使 x 点成为整个辅助树的根。
Link(x, y) 在 x, y 两点间连⼀一条边。
Cut(x, y) 把 x, y 两点间边删掉。
Find(x) 找到 x 所在的 Splay 的根节点编号。
Fix(x, v) 修改 x 的点权为 v。
Split(x, y) 提取出来 x, y 间的路路径, 方便便做区间操作

宏定义

#define ls ch[p][0]
#define rs ch[p][1]

函数讲解

pushup

inline void pushup(int p){

   //更新节点信息

   siz[p]=siz[ls]+siz[rs];

   //...

}

pushdown

inline void pushdown(int p){

   if(tag1[p]!=std_tag_1){

      //do ls & do rs

      tag1[p]=std_tag_1;

   }

   if(tag2[p]!=std_tag_2){

      //...

   }

   //...

}

Rotate & Splay

#define Get(x) (ch[f[x]][1]==x)

inline void Rotate(int x){

   int y=f[x],z=f[y],k=Get(x);

   if(!isRoot(y)) ch[z][ch[z][1]==y]=x;

   //上面这句话一定要写在前面

   ch[y][k]=ch[x][!k],f[ch[y][k]]=y;

   ch[x][!k]=y,f[y]=x,f[x]=z;

   pushup(x),pushup(y);

}

inline void Splay(int x){

   update(x);

   for(int fa=f[x];!isRoot(x);Rotate(x)){

      if(!isRoot(fa)) Rotate(Get(fa)==Get(x)?fa:x);

   }

}

上面的还是Splay用的函数，看不懂请自学Splay

下面要开始LCT独有的函数啦

isRoot

//如果一个儿子既不是父亲的左儿子，也不是右儿子，那么他就是根

//原因：我们说过如果一个儿子不是实儿子，那么父亲的ch里找不到他

#define isRoot(x) (ch[f[x]][0]!=x && ch[f[x]][1]!=x)

Access

//LCT的核心操作

inline void Aceess(int x){

   for(int p=0;x;p=x,x=f[x]){

      Splay(x),ch[x][1]=p,pushup(x);

   }

}

我们有这样一棵树，实线为实边，虚线为虚边

它的辅助树可能长成这样 (构图方式不同可能 LCT 的结构也不同)
每个绿框里是一棵 Splay。

现在我们要 Access(N), 把 A-N 的路径都变实, 拉成一棵 Splay

实现的方法是从下到上逐步更新 Splay
首先我们要把 N 旋至当前 Splay 的根。
为了保证辅助树的性质, 原来 N——O 的实边要更改为虚边。
由于认父不认子的性质, 我们可以单方面的把 N 的儿子改为 Null。
于是原来的辅助树就变成了下图。

下一步, 我们把 N 指向的 Father-> I 也旋转到它 (I) 的 Splay 树根。
原来的实边 I —— K 要去掉, 这时候我们把 I 的右儿子指向 N, 就得到了 I——L 这样一棵 Splay。（如上图）

接下来, 按照刚刚的操作步骤, 由于 I 的 Father 指向 H, 我们把 H 旋转到他所在 Splay Tree 的根, 然后把 H 的 rs 设为 I。
之后的树是这样的。

同理我们 Splay(A) , 并把 A 的右儿子指向 H。
于是我们得到了这样一棵辅助树。并且发现 A——N 的整个路径已经在同一棵 Splay 中了。大功告成！

//回顾代码

inline void Access(int x){

   for(int p=0;x;p=x,x=f[x]){

      Splay(x),ch[x][1]=p,pushup(x);

   }

}

我们发现 Access 其实很容易。只有如下四步操作：

把当前节点转到根。
把当前节点的右儿子换成之前的节点。
更新当前点的信息。
把当前点换成当前点的父亲, 继续操作。

update

//从上到下一层层pushdown即可

void update(int p){

   if(!isRoot(p)) update(f[p]);

   pushdown(p);

}

makeRoot

makeRoot 的重要性丝毫不亚于 Access 。我们在需要维护路径信息的时候, 一定会出现路径深度无法严格递增的情况, 根据辅助树的性质, 这种路径是不能出现在一棵 Splay 中的
这时候我们需要用到 Make_Root
Make_Root 的作用是使指定的点成为原树的根
考虑如何实现这种操作
我们发现 Access(x) 后，x 在 Splay 中一定是深度最大的点（从根到 x, 深度严格递增）
而变成根即是变成深度最小的点。我们 Splay(x) ，发现这时候 x 并没有右子树 (即所有点深度都比它浅)。那我们把 x 的左右儿子交换一下，变成了 x 没有左子树，x就是深度最小的点了，即达到目的
所以我们交换左右儿子，并给右儿子打一个翻转标记即可。(此时左儿子没有值)

inline void makeRoot(int p){

   Access(p),Splay(p);

   swap(ls,rs);tag[p]^=1;

}

Link

Link 两个点其实很简单, 先 Make_Root(x) , 然后把 x 的父亲指向 y 即可。显然, 这个操作肯定不能发生在同一棵树内。记得先判一下。

inline void Link(int x,int p){

   makeRoot(x);f[x]=p;

}

split

Split 操作意义很简单, 就是拿出一棵 Splay , 维护的是 x 到 y 的路径。
先 MakeRoot(x) , 然后 Access(y) 。如果要 y 做根, 再 Splay(y) 。
就这三句话, 没写代码, 需要的时候可以直接打这三个就好辣！
另外 Split 这三个操作直接可以把需要的路径拿出到 y 的子树上, 那不是随便干嘛咯。

Cut

Cut 有两种情况, 保证合法和不一定保证合法。(废话)
如果保证合法, 直接 split(x, y) , 这时候 y 是根, x 一定是它的儿子, 双向断开即可 , 就像这样：

inline void Cut(int x,int p){

   makeRoot(x),Access(p),Splay(p),ls=f[x]=0;

}

如果是不保证合法, 我们需要判断一下是否有, 我选择使用 Map 存一下, 但是这里有一个利用性质的方法：
- 想要删边, 必须要满足如下三个条件：
  1. x, y 连通。
  2. x, y 的路径上没有其他的链。
  3. x 没有右儿子。
  4. 总结一下, 上面三句话的意思就一个：x, y 有边。

Find

Find() 其实就是找到当前辅助树的根。在 Access(p) 后, 再 splay(p)。这样根就是树里最小的那个, 一直往 ls 走, 沿途 PushDown 即可。
一直走到没有 ls, 非常简单。

inline int Find(int p) {

    Access(p), Splay(p);

    while(ls) pushdown(p), p = ls;

    return p;

}

一些提醒

干点啥一定要想一想需不需要 pushup或者 pushdown, LCT 由于特别灵活的原因, 少 pushup 或者 pushdown 一次就可能把修改改到不该改的点上!
它的 rotate 和 Splay 的不太一样, if(z) 一定要放在前面。
它的 splay 就是旋转到根, 没有旋转到谁儿子的操作, 因为不需要。

一些题

BZOJ_2049
BZOJ_3282
BZOJ_2002
BZOJ_2631

码农公寓