（持续更新）LCT(Link-cut-tree) 总结+模板题+各种题目

程序员文章站 2022-12-05 08:36:43

准备知识：树剖&Splay 一、理解LCT的工作原理先看一道例题：让你维护一棵给定的树，需要支持下面两种操作： Change x val: 令x点的点权变为val Query x y: 计算x,y之间的唯一的最短路径的点权的xor和这是一道树剖裸题。我们知道，当题目中出现了维护与树上最短路相关 ......

准备知识：树剖&Splay

一、理解LCT的工作原理

先看一道例题：

让你维护一棵给定的树，需要支持下面两种操作：

Change x val: 令x点的点权变为val

Query x y: 计算x,y之间的唯一的最短路径的点权的xor和

这是一道树剖裸题。我们知道，当题目中出现了维护与树上最短路相关的区间操作时，基本可以确定要用树剖来做了。

再来看一下这道题的升级版：

让你维护一棵给定的树，需要支持下面四种操作：

Change x val: 令x点的点权变为val

Query x y: 计算x,y之间的唯一的最短路径的点权xor和

Cut x y: 如果x,y间有边相连，则删除它。

Link x y: 如果x,y不联通，则建立一条x,y之间的有向边。

在这道题里，我们增加了两个操作，Link和Cut。我们发现，这道题不可以用树剖来做了——显然，树剖无法处理修改树的形状的相关操作的。

现在我们就需要LCT了。

　　LCT，全称Link Cut Tree，中文名“动态树”。顾名思义，这种数据结构就是支持连边和断边操作同时像树剖那样维护一些数据的树。由于需要支持连边断边，LCT就不能像树链剖分一样用线段树来维护了，而需要使用更加灵活的延展树(Splay)。

　　因此，与树链剖分一样，LCT需要满足以下这些性质：

　　1.每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。

//只要把树剖和Splay搞懂了，这一点不难理解。

　　2.每一个节点存在且只存在于一个Splay中

　　3.边分为实边和虚边。实边包含在Splay树中中序遍历的相邻节点之间，而虚边必须由一棵Splay指向另一个节点，也就是中序遍历中最靠前的哪个节点的父亲。

//这里需要注意的是，一般LCT的虚边是用Splay的根节点的father指针来实现的。

　　辅助理解

当一棵树的虚实边是这样分配的时候，它所对应的伸展树是这个样子：

（持续更新）LCT(Link-cut-tree) 总结+模板题+各种题目

其中，每一个虚线框起来的区域都是一棵伸展树；双向箭头指父节点存son，子节点存father的边；单项箭头指子节点存father，而父节点不存son的边（虚边）。

二、具体操作函数

1.access(int u) 具体功能：把节点u到根节点的路径压入一个Splay中（即标记为重边）

这个没图的话实在难理解。仍然举一个例子：

如果我们在上图的情况下对节点M执行这一操作，那么这棵树就会有下图的变化：

（持续更新）LCT(Link-cut-tree) 总结+模板题+各种题目

根据样例我们可以看出，access的操作大概可以分两步：

首先，Splay(M)，将M旋转到Splay的根节点；

然后，使节点M替代它的父亲G的右子的位置，即G->rs=M。

这时，原本G的右子脱离了G所在的伸展树，与G连接的边变为了虚边；而节点M对应的伸展树则与G所在的伸展树合并，M和G之间的虚边变成了实边。

循环执行这两个操作，直到到达根节点，access操作就完成了。

这里需要注意的是，当完成一次连实边操作之后，需要将它的父亲pushup，以保证其维护数据的正确性。

这样，我们就得到了access的代码：

inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}

access

2.makeroot(int u) 具体功能：令节点u成为其所在树的根节点

当我们需要两个点之间的路径信息的时候，应该怎么做？

如果其中一个点不是另一个点的祖先的话，它们是不可能在同一个Splay里面的。

这时，我们就需要makeroot函数把其中一个点搞成根节点了。执行完access(u)操作之后，u会成为所在Splay深度最大的点；然后只需要把整棵树翻转，u就是整棵树的根了。

代码如下：

inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}

makeroot

3.split(int u,int v) 具体功能：把节点u到节点v间的路径压入到一个Splay中

有了makeroot之后，split变得超级简单：

inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}

split

4.findroot(int u) 具体功能：查询该节点所在树的根节点编号

主要应用于判断连通性。

inline int findroot(int u) {
    access(u); Splay(u); pushdown(u);
    while(ls[u]) pushdown(u),u=ls[u];
    return u;
}

findroot

5.link(int u,int v)

当u-v不连通时，连一条u到v的轻边。

inline void link(int u,int v) {
    makeroot(u);
    if(findroot(v)!=u) 
        father[u]=v;
}

link

6.cut(int u,int v)

根据LCT的性质，我们可以发现，当makeroot(u)，access(v)之后，如果存在边u-v，必须满足以下条件：

(1)u-v联通

(2)u-v在同一条Splay里有父子关系

(3)u-v在Splay的中序遍历中相邻

这样判断是否有u-v的逻辑语句就完成了，直接删除即可。

代码如下：

inline void cut(int u,int v) {
    makeroot(u);
    if(findroot(v)==u && father[u]==v && rs[u]==0)
        father[u]=ls[v]=0,pushup(v);
}

cut

7. 伸展树

这个伸展树比一般Splay特殊一些。它的判根、rotate操作和Splay操作之前的pushall函数需要注意一下。

int val[MAXN],ls[MAXN],rs[MAXN],father[MAXN],orsum[MAXN],size[MAXN],rev[MAXN];
inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    orsum[u]=val[u]^orsum[ls[u]]^orsum[rs[u]];
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        swap(ls[u],rs[u]);
        rev[u]^=1;
    }
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]^=1;
    }
}
inline void rotate(int S) { //风格比较清奇，凑活看吧qaq
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; } 
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u); //执行操作之前先pushdown.当然也可以手写栈替代系统栈 
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u])) 
            rotate(father[u]), rotate(u);
        else 
            rotate(u), rotate(u);
    }
}

View Code

三、模板题

给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

这是一道裸模板题（其实也没有什么更复杂的操作了，大概就是这么回事）

注意：该pushdown就pushdown；该pushup就pushup。

/*
716ms/4835K
多维护了一个size
*/ 
#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN=300006;
int val[MAXN],ls[MAXN],rs[MAXN],father[MAXN],orsum[MAXN],size[MAXN],rev[MAXN];
inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    orsum[u]=val[u]^orsum[ls[u]]^orsum[rs[u]];
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        swap(ls[u],rs[u]);
        rev[u]^=1;
    }
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]^=1;
    }
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; } 
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u])) 
            rotate(father[u]), rotate(u);
        else 
            rotate(u), rotate(u);
    }
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline int findroot(int u) {
    access(u); Splay(u); pushdown(u);
    while(ls[u]) pushdown(u),u=ls[u];
    return u;
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    makeroot(u);
    if(findroot(v)!=u) 
        father[u]=v;
}
inline void cut(int u,int v) {
    makeroot(u);
    if(findroot(v)==u && father[u]==v && rs[u]==0)
        father[u]=ls[v]=0,pushup(v);
}
inline int read() {
    char ch=getchar(); int ret=0; while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') ret=ret*10+(ch-'0'), ch=getchar(); return ret;
}
int main() {
    int n=read(),m=read(),opt,x,y;
    for(int i=1;i<=n;i++)
        val[i]=orsum[i]=read(),size[i]=1;
    while(m--) {
        opt=read(); x=read(); y=read();
        if(opt==0)
            split(x,y), printf("%d %d\n",orsum[y],size[y]);
        else if(opt==1)
            link(x,y);
        else if(opt==2)
            cut(x,y);
        else access(x), Splay(x), val[x]=y, pushup(x);
    }
}

View Code

[HNOI2010]弹飞绵羊

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

这道题非常容易转化成LCT的形式。第i个点与第i+k个点之间连边，每一次修改只需要cut&link一遍，被弹的次数可以用size来维护；

建一个编号为n+1的节点代表被弹飞的区域，把所有i+k>n的边连到这里，每次查询size[j~n+1]-1即可。

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN=300006;
int val[MAXN],ls[MAXN],rs[MAXN],father[MAXN],size[MAXN],rev[MAXN];
inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        swap(ls[u],rs[u]);
        rev[u]^=1;
    }
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]^=1;
    }
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; } 
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u])) 
            rotate(father[u]), rotate(u);
        else 
            rotate(u), rotate(u);
    }
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline int findroot(int u) {
    access(u); Splay(u); pushdown(u);
    while(ls[u]) pushdown(u),u=ls[u];
    return u;
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    makeroot(u);
    if(findroot(v)!=u) 
        father[u]=v;
}
inline void cut(int u,int v) {
    makeroot(u);
    if(findroot(v)==u && father[u]==v && rs[u]==0)
        father[u]=ls[v]=0,pushup(v);
}
inline int read() {
    char ch=getchar(); int ret=0; while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') ret=ret*10+(ch-'0'), ch=getchar(); return ret;
}
int kk[MAXN];
int main() {
    int n=read(),m,opt,x,y;
    for(int i=1;i<=1+n;i++)
        size[i]=1;
    for(int i=1;i<=n;i++) {
        kk[i]=read();
        if(i+kk[i]<=n)
            link(i,i+kk[i]);
        else link(i,n+1);
    }
    m=read();
    while(m--) {
        opt=read(); x=read(); x++;
        if(opt==1)
            split(x,n+1), printf("%d\n",size[n+1]-1);
        else {
            y=read();
            if(y!=kk[x]) 
                cut(x,(x+kk[x]>n?n+1:x+kk[x])), kk[x]=y, link(x,(x+kk[x]>n?n+1:x+kk[x]));
        }
    }
}

View Code

一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：

+ u v c：将u到v的路径上的点的权值都加上自然数c；

- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；

* u v c：将u到v的路径上的点的权值都乘上自然数c；

/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。

100%的数据保证，1<=n，q<=10^5，0<=c<=10^4

LCT本身很简单，甚至都不需要判连通性

这道题的难点仅在于pushdown的处理。

细节：需要注意51657^2会爆int，需要用unsigned

还有：千万注意区间乘操作可以乘0！血的教训qaq

#include <iostream>
#include <cstdio>

using namespace std;

const unsigned int MAXN=300035;
const unsigned int PYZ=51061;

unsigned int val[MAXN],father[MAXN],ls[MAXN],rs[MAXN],rev[MAXN],sum[MAXN];
unsigned int taga[MAXN],tagc[MAXN],size[MAXN];

inline bool isroot(int u) {
    return ls[father[u]]!=u && rs[father[u]]!=u;
}
inline void pushup(int u) {
    sum[u]=val[u]+sum[ls[u]]+sum[rs[u]]; sum[u]%=PYZ;
    size[u]=1+size[ls[u]]+size[rs[u]];
}
inline void reverse(int u) {
    if(u) {
        rev[u]^=1;
        swap(ls[u],rs[u]);
    }
}
inline void pusha(int u,int c) {
    taga[u]+=c, taga[u]%=PYZ;
    val[u]+=c, val[u]%=PYZ;
    sum[u]+=(c*size[u])%PYZ, sum[u]%=PYZ;
}
inline void pushc(int u,int c) {
    taga[u]*=c, taga[u]%=PYZ;
    val[u]*=c, val[u]%=PYZ;
    sum[u]*=c, sum[u]%=PYZ;
    tagc[u]*=c, tagc[u]%=PYZ;
}
inline void pushdown(int u) {
    if(rev[u]) {
        reverse(ls[u]);
        reverse(rs[u]);
        rev[u]=0;
    }
    if(tagc[u]!=1) 
        pushc(ls[u],tagc[u]), pushc(rs[u],tagc[u]), tagc[u]=1;
    if(taga[u])
        pusha(ls[u],taga[u]), pusha(rs[u],taga[u]), taga[u]=0;
}
inline void rotate(int S) {
    int u=father[S]; if(father[u]) { if(ls[father[u]]==u) ls[father[u]]=S; else if(rs[father[u]]==u) rs[father[u]]=S; }
    father[S]=father[u]; father[u]=S;
    if(ls[u]==S) {
        if(rs[S]) father[rs[S]]=u; ls[u]=rs[S]; rs[S]=u;
    }
    else {
        if(ls[S]) father[ls[S]]=u; rs[u]=ls[S]; ls[S]=u;
    }
    pushup(u); pushup(S);
}
void pushall(int u) {
    if(!isroot(u)) {
        pushall(father[u]);
        pushdown(father[u]);
    }
}
inline void Splay(int u) {
    pushall(u); pushdown(u);
    while(!isroot(u)) {
        if(isroot(father[u]))
            rotate(u);
        else if((ls[father[u]]==u) == (ls[father[father[u]]]==father[u]))
            rotate(father[u]), rotate(u);
        else rotate(u), rotate(u);
    }
    pushup(u);
}
inline int kth(int u,int k) {
    if(k<=size[ls[k]])
        return kth(ls[u],k);
    else if(k==size[ls[k]]+1)
        return u;
    else return kth(rs[u],k-size[ls[k]]-1);
}
inline void access(int u) {
    for(int v=0;u;v=u,u=father[u]) 
        Splay(u), rs[u]=v, pushup(u);
}
inline void makeroot(int u) {
    access(u); Splay(u); reverse(u);
}
inline int findroot(int u) {
    access(u); Splay(u); while(ls[u]) pushdown(u), u=ls[u]; return u;
}
inline void split(int u,int v) {
    makeroot(u); access(v); Splay(v);
}
inline void link(int u,int v) {
    makeroot(u); father[u]=v;
}
inline void cut(int u,int v) {
    split(u,v); ls[v]=father[u]=0, pushup(v);
}
inline int read() {
    char ch=getchar(); while(ch!='+' && ch!='-' && ch!='*' && ch!='/') ch=getchar();
    getchar(); if(ch=='+') return 1;  if(ch=='-') return 2;  if(ch=='*') return 3; return 4;
}
int main() {
    int n,q,op,x,y,z; scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) {
        size[i]=tagc[i]=val[i]=sum[i]=1;
        taga[i]=0; 
    }
    for(int i=1;i<n;i++)
        scanf("%d%d",&x,&y) ,link(x,y);
    while(q--) {
        op=read();
        if(op==1) {
            scanf("%d%d%d",&x,&y,&z);
            split(x,y); pusha(y,z);
        }
        else if(op==2) {
            scanf("%d%d",&x,&y); cut(x,y);
            scanf("%d%d",&x,&y); link(x,y);
        }
        else if(op==3) {
            scanf("%d%d%d",&x,&y,&z);
            split(x,y); pushc(y,z);
        }
        else {
            scanf("%d%d",&x,&y);
            split(x,y); printf("%d\n",(int)sum[y]%51061);
        }
    }
}

View Code

上一篇：华大基因汪建:大数据云计算支撑下的基因产业没有冬天

下一篇：百度与Facebook 谁更吸引人工智能的小鲜肉？