xiaoMa
"Bye Bye Baby Blue"
LCT(动态树)总结


最近学了学$LCT$,简单讲下。

一【理论知识】

  • -$Link-Cut-Tree$(简称 LCT) 是解决动态树类问题一种数据结构
  • -$Preferred Child$:重儿子,重儿子与父亲节点在同一棵 $Splay$ 中,一个节点最多只能有一个重儿子
  • -$Preferred Edge$:重边,连接父亲节点和重儿子的边
  • -$Preferred Path$ :重链,由重边及重边连接的节点构成的链
  • -$Auxiliary Tree$(辅助树)

由一条重链上的所有节点所构成的 $Splay$ 称作这条链的辅助树 每个点的键值为这个点的深度,即这棵 $Splay$ 的中序遍历是这条链从链顶到链底的所有节点构成的序列 辅助树的根节点的父亲指向链顶的父亲节点,然而链顶的父亲节点的儿子并不指向辅助树的根节点 (也就是说父亲不认轻儿子只认重儿子,儿子都认父亲) 这条性质为后来的操作提供了依据

原树与辅助树的关系

  • 原树中的重链 $->$ 辅助树中两个节点位于同一棵 $Splay$ 中
  • 原树中的轻链 $->$辅助树中子节点所在 $Splay$ 的根节点的 $father$ 指向父节点
  • 注意原树与辅助树的结构并不相同
  • 辅助树的根节点$≠$原树的根节点
  • 辅助树中的 $father$≠原树中的 $father $
  • 辅助树是不断变化的,重链和轻链不断变化

二【实现】

$LCT$ 用到的 $Splay$ 和通常的还是有点不同,没有权值 $v$,不进行查找操作,点编号就是原树的编号

因为是一个 $Splay$ 森林,多条重链多个根,所以用 $isRoot(x)$ 判断是否为根,判断 $isRoot(x)$ 相当于判断 $x $的父亲存不存在

  • -$rotate$ 只是设置 $g$ 的儿子时判断 $isRoot(f)$ 就行了
  • -$splay$ 需要 $pushDown$ 了 (因为没有 $kth$ 了),也是判断 $isRoot(pa)$
  • -$Access$ 和 $Cut$ 更新了儿子关系,所以需要 $update$
  • -$Access$ 将一个点与原先的重儿子切断,并使这个原树上点到根路径上的边全都变为重边

所以 这个节点到根的路径上的所有节点形成了一棵 $Splay$

便于操作或查询节点到根路径上的所有节点

实现:不断把 $x$ $splay$ 到当前 $Atree$ 的根,然后它的右子树就是重儿子了,修改;用 $y$ 辅助 注意:$Access$ 后 $x $不一定为这颗 $Splay$ 的根,因为中途 $x$ 变 $fa$ 了 维护了节点信息别忘更新

  • $MakeRoot$ 将 $x$ 设为原树的根实现:$Access$ 后 $splay$ 到根,然后全在 $x$ 的左子树上 (权值是深度),区间翻转即可
  • $FindRoot$ 找 $x$ 所在原树根,判连通性 实现:$MakeRoot$ 后不断往左找 (不需要 $pushDown$?加上也可以啊。不加也对因为只是来判连通,判断是不是在一棵原树上,都不 $pushDown$ 找到的还是同一个点吧)
  • $Link$ 实现:$MakeRoot(x)$ 然后 $t[x].fa=y$
  • $Cut$ 实现:$MakeRoot(x)$ 然后 $Access(y)$$ splay(y)$ ,$x$ 就在 $y$ 的左儿子了,$t[y].ch[0]=t[x].fa=0;$

维护了节点信息别忘更新

对$ x$ 到 $y$ 路径上的点进行修改或查询

只需要对 $x$ 进行 $Move_To_Root$ 操作,然后对 $y$ 进行 $Access$+$Splay$ 操作,那么 $x$ 到 $y$ 路径上的所有点都在以 $y$ 为根的子树上 因为 $Access$ 后 $x$ 和 $y$ 重链在一棵 $Splay$ 上,$x$ 深度比 $y$ 小


像树剖一样…… 将某一个儿子的连边划分为实边,而连向其他子树的边划分为虚边。 区别在于虚实是可以动态变化的,因此要使用更高级、更灵活的$ Splay$ 来维护每一条由若干实边连接而成的实链。 基于性质更加优秀的实链剖分,$LCT(Link-Cut Tree)$ 应运而生。 $LCT$ 维护的对象其实是一个森林。 在实链剖分的基础下,LCT 支持更多的操作

  • 查询、修改链上的信息(最值,总和等)
  • 随意指定原树的根(即换根)
  • 动态连边、删边
  • 合并两棵树、分离一棵树(跟上面不是一毛一样吗)
  • 动态维护连通性(代替并查集)

边分为实边和虚边,实边包含在$Splay$ 中,而虚边总是由一棵 $Splay$ 指向另一个节点(指向该 $Splay$ 中中序遍历最靠前的点在原树中的父亲)。 因为性质 $2$,当某点在原树中有多个儿子时,只能向其中一个儿子拉一条实链(只认一个儿子),而其它儿子是不能在这个 $Splay$ 中的。 那么为了保持树的形状,我们要让到其它儿子的边变为虚边,由对应儿子所属的 $Splay$ 的根节点的父亲指向该点,而从该点并不能直接访问该儿子(认父不认子)。

有一棵树,假设一开始实边和虚边是这样划分的(虚线为虚边)

那么所构成的 $LCT$ 可能会长这样(绿框中为一个 $Splay$,可能不会长这样,但只要满足中序遍历按深度递增(性质 1)就对结果无影响)

现在我们要 $access(N)$,把 $A−N$ 的路径拉起来变成一条 $Splay$。 因为性质 $2$,该路径上其它链都要给这条链让路,也就是把每个点到该路径以外的实边变虚。 所以我们希望虚实边重新划分成这样。

然后怎么实现呢? 我们要一步步往上拉。 首先把 $splay(N)$,使之成为当前 $Splay$ 中的根。 为了满足性质 $2$,原来 $N−O$ 的重边要变轻。 因为按深度 $O$ 在 $N$ 的下面,在 $Splay$ 中$ O$ 在 $N$ 的右子树中,所以直接单方面将 $N$ 的右儿子置为 $0$(认父不认子) 然后就变成了这样——

我们接着把 $N$ 所属 $Splay$ 的虚边指向的 $I$(在原树上是 $L$ 的父亲)也转到它所属 $Splay$ 的根,$splay(I)$。 原来在 $I$ 下方的重边 $I−K$ 要变轻(同样是将右儿子去掉)。 这时候 $I−L$ 就可以变重了。因为 $L$ 肯定是在 $I$ 下方的(刚才 $L$ 所属 $Splay$ 指向了$ I$),所以 $I$ 的右儿子置为 $N$,满足性质 $1$。 然后就变成了这样——

$I$ 指向 $H$,接着 $splay(H)$,$H$ 的右儿子置为 $I$。 $H$ 指向 $A$,接着 $splay(A)$,$A$ 的右儿子置为 $H$。

$A−N$ 的路径已经在一个 $Splay$ 中了,大功告成!

代码其实很简单。循环处理,只有四步—— 转到根; 换儿子; 更新信息; 当前操作点切换为轻边所指的父亲,转 1

inline void access(int x) { for(int tp = 0 ; x ; x = fa[tp = x]) splay(x) , rs(x) = tp , pushup(x) ; }

只是把根到某个节点的路径拉起来并不能满足我们的需要。更多时候,我们要获取指定两个节点之间的路径信息。 然而一定会出现路径不能满足按深度严格递增的要求的情况。根据性质 $1$,这样的路径不能在一个 $Splay$ 中。 可以将 $makeroot$定义为换根,让指定点成为原树的根。 这时候就利用到 $access(x)$ 和 $Splay$ 的翻转操作。 $access(x)$ 后 $x$ 在 $Splay$ 中一定是深度最大的点对吧。 $splay(x)$ 后,$x$ 在 $Splay$ 中将没有右子树(性质 $1$)。于是翻转整个 $Splay$,使得所有点的深度都倒过来了,$x$ 没了左子树,反倒成了深度最小的点(根节点),达到了我们的目的。

inline void makeroot(int x) { access(x) ; splay(x) ; pushr(x) ; }

$findroot(x)$ 找 $x$ 所在原树的树根,主要用来判断两点之间的连通性($findroot(x)==findroot(y)$ 表明 $x$,$y$ 在同一棵树中)

inline int findroot(int x) { access(x) ; splay(x) ; while(ls(x)) { pushdown(x) ; x = ls(x) ; splay(x) ; } return x ; }

同样利用性质$ 1$,不停找左儿子,因为其深度一定比当前点深度小。

$split(x,y)$ 神奇的 $makeroot$ 已经出现,我们终于可以访问指定的一条在原树中的链啦! $split(x,y)$ 定义为拉出 $x−y $的路径成为一个 $Splay$

inline void split(int x , int y) { makeroot(x) ; access(y) ; splay(y) ; }

$Link$ 和 $Cut$ 就是字面意思 连边建边 具体写法

inline void cut(int x , int y) { makeroot(x) ; if(findroot(y) == x && fa[y] == x && ! ls(y)) fa[y] = ls(x) = 0 , pushup(x) ; }
  inline void link(int x , int y) { makeroot(x) ; if(findroot(y) != x) fa[x] = y ; }

板子

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
int n , m , val[N] ;
inline int read() {
    register int x = 0 , f = 1 ;
    register char c = getchar() ;
    for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
    for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c &amp; 15) ;
    return x * f ;
}
class LCT {
public:
  int ch[N][2] , fa[N] , sum[N] , rev[N] ;
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
  inline bool isroot(int x) { return ls(fa[x]) != x &amp;&amp; rs(fa[x]) != x ; }
  inline bool getr(int x) { return rs(fa[x]) == x ; }
  inline void pushup(int x) { sum[x] = sum[ls(x)] ^ sum[rs(x)] ^ val[x] ; }
  inline void pushr(int x) { rev[x] ^= 1 ; swap(ls(x) , rs(x)) ; }
  inline void pushdown(int x) { if(rev[x]) { if(ls(x)) pushr(ls(x)) ; if(rs(x)) pushr(rs(x)) ; rev[x] ^= 1 ; } }
  inline void rotate(int x) {
    int y = fa[x] , z = fa[y] , k = getr(x) , w = ch[x][k ^ 1] ; if(! isroot(y)) ch[z][getr(y)] = x ;
    fa[fa[fa[ch[ch[x][k ^ 1] = y][k] = w] = y] = x] = z ; pushup(y) ; pushup(x) ;
  }
  inline void pushall(int x) { if(! isroot(x)) pushall(fa[x]) ; pushdown(x) ; }
  inline void splay(int x) {
    pushall(x) ; while(! isroot(x)) { int y = fa[x] ; if(! isroot(y)) rotate(getr(x) ^ getr(y) ? x : y) ; rotate(x) ; }
  }
  inline void access(int x) { for(int tp = 0 ; x ; x = fa[tp = x]) splay(x) , rs(x) = tp , pushup(x) ; }
  inline void makeroot(int x) { access(x) ; splay(x) ; pushr(x) ; }
  inline void split(int x , int y) { makeroot(x) ; access(y) ; splay(y) ; }
  inline int findroot(int x) { access(x) ; splay(x) ; while(ls(x)) { pushdown(x) ; x = ls(x) ; splay(x) ; } return x ; }
  inline void cut(int x , int y) { makeroot(x) ; if(findroot(y) == x &amp;&amp; fa[y] == x &amp;&amp; ! ls(y)) fa[y] = ls(x) = 0 , pushup(x) ; }
  inline void link(int x , int y) { makeroot(x) ; if(findroot(y) != x) fa[x] = y ; }
  inline void change(int x , int y) { splay(x) ; val[x] = y ; }
  inline int query(int x , int y) { return split(x , y) , sum[y] ; }
} lct ;
signed main() {
  n = read() ; m = read() ;
  for(register int i = 1 ; i <= n ; i ++) cin >> val[i] ;
  for(register int i = 1 ; i <= m ; i ++) {
    int opt = read() ;
    if(opt == 0) { int x = read() , y = read() ; printf("%d\n" , lct.query(x , y)) ; }
    if(opt == 1) { int x = read() , y = read() ; lct.link(x , y) ; }
    if(opt == 2) { int x = read() , y = read() ; lct.cut(x , y) ; }
    if(opt == 3) { int x = read() , y = read() ; lct.change(x , y) ; }
  }
  return 0 ;
}

动态树,永远滴神!

发表评论

textsms
account_circle
email

LCT(动态树)总结
最近学了学$LCT$,简单讲下。 一【理论知识】 -$Link-Cut-Tree$(简称 LCT) 是解决动态树类问题一种数据结构 -$Preferred Child$:重儿子,重儿子与父亲节点在同一棵 $Splay$ …
扫描二维码继续阅读
2020-04-27