柒葉灬 的博客

柒葉灬 的博客

LCT总结(个人笔记)

posted on 2019-03-10 14:46:24 | under 专题总结 |

LCT总结


前置技能: $splay$

介绍:

LCT即 Link-Cut-Tree,

其中Link指连接,Cut指断开,Tree则是一棵树。

说白了就是一棵动态树

可以动态删除边,添加边。

擅长处理链上的问题

但是子树问题也可以解决,后面会有例题。


当然,作为一个优秀的数据结构 $LCT$ ,

肯定不能像普通的树一样暴力跳父亲,

肯定要有优秀的方法快速找根。

但普通的树是用 倍增重链剖分

(或许还有长链剖分

而这两种算法都不能修改。

所以我们用的是另一种方法:实链剖分


实链剖分


这里先介绍一下什么是 实链剖分

实际上就是选一个儿子与自己的边当做实边

其他边都是虚边

实边需要满足什么条件?

实边不需要任何条件,

就是自己随便选的,

就是因为是随便选的,所以才可以动态连边删边

这些实边就形成了实链。

当然也可以都是虚边


我之前在一篇博客里面看到一句话,

很好的概括了实边和虚边的区别:

认子不认父

即每个点不用管自己和父亲连的是实边还是虚边

只要记录与哪一个儿子连实边就行了。

如果需要判断自己和父亲是不是连实边

只需要判一下父亲的实儿子是不是自己就行了

感觉有什么怪怪的???


那么有了实链之后有什么用?

怎么把实链用在 $LCT$ 上?

想一下如果是重链剖分的话,应该怎么找根呢?

我们可以一直跳到实链的顶端,直到到达根为止。

但是这样还有几个问题需要解决:

  1. 怎么保证跳的实链的次数不会过大?
  2. 怎么跳到每条链的顶端的父亲?

第一个问题:怎么保证跳的实链的次数不会过大?

我们可以每次把当前的点和根变成一条实链,

以此来保证复杂度的合理性。(感性理解)

第二个问题:怎么跳到每条链的顶端的父亲?

重链剖分里面是直接记录每一个点的 $top$ 指向哪里。

而实链剖分就不能这么做,因为 $top$ 随时可能会变。

这时候就要用到最核心的知识了,

把每一条实链用一个splay来表示

  1. 左儿子深度都比当前点
  2. 右儿子深度都比当前点

splay当中最左边的数就是链的顶端了。

但,链顶的点不一定是splay的根怎么办?

即,可能链顶的点的 $fa$ 表示的是splay当中的 $fa$

我们注意到, $splay$ 当中,根是没有父亲的。

所以我们可以这么做,

每个 $splay$ 的根的 $fa$ 表示链顶的点在树中的父亲


做个图以便理解:

其中加粗的是实边,其他的是虚边。

而实际上每一个实链是用splay来表示的,

所以可能实际上 $son$ 和 $fa$ 的关系是这样的。

其中每一个框就是一个 $splay$


mmp为什么写了半天的概念

接下来就是怎么设计代码了。

$up,down$ 以及 $pushr$ (翻转)与普通 $splay$ 一样。

多了一个判断是不是 $splay$ 的根的函数 $noroot$

bool noroot(int x){
    return son[fa[x]][0]==x||son[fa[x]][1]==x;
}//如果不是splay的根返回true;

首先,LCT当中的 $splay$ 的 $rotate$ 和 $splay$

是不能复制普通 $splay$ 的,

有些不同。

rotate操作

void rotate(int x){
    int y=fa[x];
    int z=fa[y];
    int k=(son[y][1]==x);
    if(noroot(y))son[z][(son[z][1]==y)]=x;
    fa[x]=z;
    son[y][k]=son[x][k^1];
    fa[son[x][k^1]]=y;
    son[x][k^1]=y;
    fa[y]=x;
    up(y);up(x);
}

为什么需要判断 $noroot(y)$ 呢?

因为如果 $y$ 是根则说明 $z$ 不在 $x$ 这个 $splay$ 内

如果不加则会改变 $z$ 的实儿子,故错。


splay操作

void splay(int x){
    int u=x,top=0;
    stk[++top]=u;
    while(noroot(u))stk[++top]=u=fa[u];
    while(top)down(stk[top--]);
    //即先down完之后再splay
    while(noroot(x)){
        int y=fa[x];
        int z=fa[y];
        if(noroot(y))
            (son[z][1]==y)^(son[y][1]==x)?rotate(x):rotate(y);
        rotate(x);
    }
}

以上都是处理实链的操作,那么怎么造出实链呢?

下面这个操作就是 $LCT$ 的核心操作了。

access操作

void access(int x){
    for(int y=0;x;y=x,x=fa[x])
        splay(x),son[x][1]=y,up(x);
}

这段代码什么意思呢?

即造出 $x$ 到 $root$ 这条实链,之前的其他实边变为虚边。

循环里面是把 $x$ 与 $y$ 连上实边,之前的实边被覆盖。

  1. $splay(x)$ :把x旋转到根
  2. $son[x][1]=y$ :之前的实边被覆盖,实儿子变成y。

注意链是从 $root$ 到 $x$ 的,

所以 $x$ 实际上位于实链的最底端, $splay$ 的最右端。


接下来的代码想想就都能明白了

makeroot操作

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

把 $x$ 变成树的根。


findroot操作

int findroot(int x){
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);//保证复杂度
    return x;
}

还有一个操作可以把要修改的链给拎出来

split操作

void split(int x,int y){
    makeroot(x);access(y);splay(y);
    //直接对y节点进行询问即可
}

最后就是连边和删边操作了

link操作

所连的边可能已经存在了,那么这么写

bool link(int x,int y){
    makeroot(x);
    if(findroot(y)==x)return false;
    fa[x]=y;//直接连接虚边
    return true;
}

如果数据中保证边合法,那么可以这么写

void link(int x,int y){
    makeroot(x);
    fa[x]=y;
}

cut操作

所删的边可能不存在,需要这么写

bool cut(int x,int y){
    makeroot(x);
    if(findroot(y)!=x||fa[y]!=x||son[y][0])return false;
    son[x][1]=fa[y]=0;
    up(x);
    return true;
}

如果数据中保证边合法,那么可以这么写

void cut(int x,int y){
    split(x,y);
    son[y][0]=fa[x]=0;
    up(y);
}

那么 $LCT$ 基本就已经讲完了,接下来就是做题经验了。

LCT在基环树当中的应用

基环树当中有一个环,但显然树里面不能有环,

所以可以用 $LCT$ 把基环树变成树。

即把环中的一个点变成根,

再把连成环的那条边单独记录下来,

如果环被破坏掉了则连回去。

LCT专题L

LCT维护子树信息

$LCT$ 实际上也可以维护子树的信息

只不过略微麻烦一点,

就是多维护一个虚儿子的信息,

在 $access$ 的时候注意修改就行了。

LCT专题K


END