LCT 学习笔记

LCT学习笔记

前言

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

于是就学LCT了

简介

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

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

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

动态树问题

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

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

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

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

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

实链剖分

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

LCT！

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

辅助树

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

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

lct9

那么辅助树的结构如下

lct10

原树和辅助树的结构关系

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

变量声明

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

函数声明

⼀般数据结构函数 (字面意思)
  1. PushUp(x)
  2. PushDown(x)
Splay 系函数
  1. Get(x) 获取 x 是父亲的哪个⼉子。
  2. Splay(x) 通过和 Rotate 操作联动实现把 x 旋转到 当前 Splay 的根。
  3. Rotate(x) 将 x 向上旋转一层的操作。
新操作
  1. IsRoot(x) 判断当前节点是否是所在 Splay 的根
  2. Access(x) 把从根到当前节点的所有点放在⼀条实链里, 使根到它成为一条实路径, 并且在同一棵 Splay 里里。
  3. Update(x) 在 Access 操作之后, 递归的从上到下 Pushdown 更新信息。
  4. MakeRoot(x) 使 x 点成为整个辅助树的根。
  5. Link(x, y) 在 x, y 两点间连⼀一条边。
  6. Cut(x, y) 把 x, y 两点间边删掉。
  7. Find(x) 找到 x 所在的 Splay 的根节点编号。
  8. Fix(x, v) 修改 x 的点权为 v。
  9. 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);
   }
}

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

pic1

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

pic2

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

pic3

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

pic4

pic

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

pic

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

pic

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

pic

//回顾代码
inline void Access(int x){
   for(int p=0;x;p=x,x=f[x]){
      Splay(x),ch[x][1]=p,pushup(x);
   }
}

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

  1. 把当前节点转到根。
  2. 把当前节点的右儿子换成之前的节点。
  3. 更新当前点的信息。
  4. 把当前点换成当前点的父亲, 继续操作。
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 两个点其实很简单, 先 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
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wawawa8/p/9686702.html