LCT 学习笔记

· · 个人记录

前言

在暑假集训期间学习了 LCT 这一算法（数据结构？），然后就水了练习了很多题，现在开个总结记录一下自己学习的过程。

算法介绍

LCT 是一个非常优秀的可以在 n\log n 的时间复杂度内完成一颗树上的大多数操作的算法，包括且不限于 询问链上和，积，\max,\min，动态删边，动态加边。

然后算法的本质就是在一颗树上进行实虚链的剖分，跟重链剖分不同的是，这个剖分是可以 动态变化 的，也就是说，我可以随时转化一个点的实虚链。

const int N = 1e5 + 1;
#define ls s[x][0]
#define rs s[x][1]
int s[N][2], f[N], rv[N], su[N], va[N];
void psu(int x) {su[x]=va[x]^su[ls]^su[rs];}
void psr(int x) {if(x) swap(ls,rs),rv[x]^=1;}
void psd(int x) {if(rv[x]) psr(ls),psr(rs),rv[x]=0;}
bool nrt(int x) {return s[f[x]][0]==x||s[f[x]][1]==x;}
void psa(int x) {if(nrt(x)) psa(f[x]);psd(x);}
void rot(int x) {
    int y=f[x],z=f[y],k=x==s[y][1];
    if(nrt(y)) s[z][y==s[z][1]]=x;
    s[y][k]=s[x][!k],s[x][!k]=y;
    if(s[y][k]) f[s[y][k]]=y;f[x]=z,f[y]=x;
    psu(y),psu(x);
}
void spl(int x) {
    psa(x);
    for(int y,z;y=f[x],z=f[y],nrt(x);rot(x)) 
    if(nrt(y)) rot(x==s[y][1]^y==s[z][1]?x:y);
}
void acc(int x) {for(int y=0;x;y=x,x=f[y]) spl(x),rs=y,psu(x);}
void mrt(int x) {acc(x),spl(x),psr(x);}
long frt(int x) {acc(x),spl(x);while(ls) psd(x),x=ls;return x;}
void spt(int x,int y) {mrt(x),acc(y),spl(y);}
void lnk(int x,int y) {mrt(x);if(frt(y)!=x)f[x]=y;}
void cut(int x,int y) {mrt(x);if(frt(y)==x&&f[x]=y&&!rs)f[x]=f[y][0]=0,psu(y);}
long ask(int x,int y) {spt(x,y);return su[y];}
// void lnk(int x,int y) {mrt(x),f[x]=y;} 
// void cut(int x,int y) {spt(x,y);f[x]=s[y][0]=0,psu(y);}

由于 LCT 是 认爹不认儿子的，就是说 LCT 中大多数的点只认识他们的爹但是不认识他们所有的儿子，这就给了 SPLAY 发挥的空间，我们可以用 SPLAY 动态维护每一个块的信息，然后进行一些维护。

acc

LCT 中最重要的就是 access 操作，这也是 LCT 的核心操作，基本上所有的询问修改都离不开这个操作。

access 的实质就是从 x 打通一条通向根节点的通道，也就是将根节点和 x 节点放到一个 splay 里面，不过 x 所连的其他实边也会变成虚边。

mrt

mrt 操作全称 make_root，它可以将一个点变成根节点，由于 acc 之后该点与根节点是出于同一个 splay 当中的，所以我们可以直接 spl 这个点把这个点提到根的位置上，就可以完成换根操作了。

frt

我们将一个点换到根之后，只需要将该点不停向左儿子找就可以找到原来的根了。

spt

split 操作就是将一条链给打通，并且将 y 提到根节点处，y 所含有的信息就是 x\to y 的信息了。

lnk

link 操作就是连边，将一个点提到根节点之后直接连向 y 就可以了，不用保证是否是实儿子。

cut

cut 操作就是断边，由于将 x,y spt 之后会成为一条链，如果 x,y 之间本来就有一条边，那么 y 的左儿子就是 x，直接断开就可以了。

大概就是这么多操作，如果要修改或者查询的话直接 spt 一下然后修改或者查询 y 的信息就可以了。

trick

动态 LCA

LCT 是可以动态查询 LCA 的，只用将所需的根 mrt 然后将 x acc 一下，然后由于打通了一条通向根的 splay，那么打通 y 的时候可以直接打通，最后一个虚实链交换的节点就是 LCA 了。

long acc(int x) {
    int ret=0;
    for(int y=0;x;y=x,x=f[y])spl(x),rs=y,ret=x;
    return ret;
}
long LCA(int x,int y) {acc(x);return acc(y);}

例题：【模板】最近公共祖先（LCA），我上传的题

查询子树信息

由于维护子树信息我还不会，先咕了。

查询子树信息的时候只用在 acc 中做一点手脚就可以了。

我们可以只维护虚儿子的信息，不维护实儿子的信息就可以了，打通的时候转化一下就可以了。

void psu(int x) {su[x]=su[ls]+su[rs]+va[x]+si[x];}
void acc(int x) {for(int y=0;x;y=x,x=f[y]) spl(x),si[x]+=su[rs],si[x]-=su[rs=y],psu(x);}

上面是维护子树加和的例子。

还是 spt 之后直接访问就可以了，直接就是 si[x] 就是子树信息了。

例题：大融合

维护最小生成树

有时候题目需要动态维护最小生成树，那么我们就可以将边权变点权，如果可以连边直接连，不能连边询问 u,v 链上的最大值比较一下然后干掉就可以了。

例题：魔法森林，水管局长，最小差值生成树，温暖会指引我们前行