高级数据结构——LCT总结

seajupiter · 2020-06-06 15:48:32 · 个人记录

update：注意，LCT get_rt 之后一定要splay一下才能保证复杂度！之前写错了！

update 2020/08/14 更新了模板题更快的代码

LCT 是什么？

LCT，Link-Cut-Tree 的缩写形式，顾名思义为动态树，其功能极为强大，可以在 O(nlog(n)) 的时间复杂度（带上一个巨大的常数）内解决一系列树上与路径和子树的问题。

其与树剖相比特别之处在于能支持动态加边、删边（要求加删之后还是一棵树），以及换根。

LCT 基本功能如下。

维护信息方面：

点权信息
边权信息
链信息和
子树信息和

进行操作方面：

单点操作
链上操作

注意：树剖可以方便的进行子树操作，而 LCT 不可以（想一想为什么）!

LCT 怎么写？

需要用到 splay 维护。

清点必须的基本函数：

prf(x) ：x 是否为其父亲的偏爱儿子
get(x) ：x 是其父亲的哪一个偏爱儿子
upd(x) ：更新信息
down(x) ：下传标记
all_down(x) ：在 splay(x) 中会用到的把 x 上方的所有标记都下传
rot(x) ：旋转 x
splay(x) ：把 x 旋转至辅助树根
access(x) ：把 x 到其原数根部的路径“打通”（ LCT 的核心函数）

洛谷LCT模板题代码：

#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i=l; i<=r; ++i)
using namespace std;

char _b[100000], *p1, *p2;
#define gc ((p1==p2)&&(p2=(p1=_b)+fread(_b,1,100000,stdin)),p1==p2)?EOF:*(p1++)
template<class T> inline void read(T& x){
    char c=gc;x=0; while(!isdigit(c))c=gc;
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc;
}

const int N=1e5+5;

int n, m, val[N], sum[N], ch[N][2], f[N], rev[N];

#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define get(x) (x==rs(f[x]))
#define prf(x) (x==ls(f[x])||x==rs(f[x]))
inline void upd(int x){
    sum[x]=val[x]^sum[ls(x)]^sum[rs(x)];
}
inline void Rev(int x){
    if(x) rev[x]^=1, swap(ls(x), rs(x));
}
inline void down(int x){
    if(rev[x]) Rev(ls(x)), Rev(rs(x)), rev[x]=0;
}
inline void all_down(int x){
    if(prf(x)) all_down(f[x]);
    down(x);
}
inline void rot(int x){
    int y=f[x], z=f[y], d=get(x), son=ch[x][d^1];
    if(prf(y)) ch[z][get(y)]=x; f[x]=z;
    ch[x][d^1]=y; f[y]=x;
    ch[y][d]=son; if(son) f[son]=y;
    upd(y);
}
inline void splay(int x){
    all_down(x);
    for(int y=f[x]; prf(x); rot(x), y=f[x])
        if(prf(y)) rot((get(x)^get(y))?x:y);
    upd(x);
}
inline void access(int x){
    for(int y=0; x; x=f[y=x])
        splay(x), rs(x)=y, upd(x);
}
inline void mkrt(int x){
    access(x), splay(x), Rev(x);
}
inline int getrt(int x){
    access(x), splay(x);
    for(; ls(x); x=ls(x)) down(x);
    return splay(x), x;
}
inline void split(int x, int y){
    mkrt(x), access(y), splay(y);
}
inline void link(int x, int y){
    mkrt(x), (getrt(y)^x)&&(f[x]=y);
}
inline void cut(int x, int y){
    mkrt(x);
    if((getrt(y)^x)||(f[y]^x)||ls(y)) return;
    f[y]=rs(x)=0, upd(x);
}

int main(){
    read(n);read(m);
    FOR(i, 1, n){
        read(val[i]);
        sum[i]=val[i];
    }

    while(m--){
        int op, x, y;
        read(op);read(x);read(y);
        if(op==0) split(x, y), printf("%d\n", sum[y]);
        else if(op==1) link(x, y);
        else if(op==2) cut(x, y);
        else splay(x), val[x]=y, upd(x);
    }

    return 0;
}

若要维护子树信息，则在多维护每个点所有虚儿子信息和即可，并在 upd(x), access(x), link(x) 中做出相应修改（想一想为什么）。（题目：UOJ207.共价大爷游长沙，P4219 [BJOI2014]大融合）

若要维护边权，则把边变成点，并分别与边连接的两个节点向量即可，转化维护边权为维护点权。（题目：P2387 [NOI2014]魔法森林， P4234 最小差值生成树）

LCT怎么用？

LCT与最小生成树

LCT 由于其可以动态支持加边删边并维护边权等操作，常用来做各种情况下的最小生成树问题。

往往常见于维护两维的最优性的问题，比如双权值最大值最小（P2387 [NOI2014]魔法森林）、边权最大值和最小值差值最小（ P4234 最小差值生成树）等等。做法就是先让一维有序，然后利用这一维的有序性枚举每一条边，并根据所求生成树性质决定加边成环时的取舍问题。而 LCT 可以非常方便的解决这些问题。

LCT与路径交

经典题目：UOJ207.共价大爷游长沙

动态增删边，动态向所求路径集合中加入路径或删除路径，在线询问某一条边是否在所有路径的交上。

如果没有增删边操作，可以用 LCT /树剖实现链加减，然后如果所问的边上的权值为路径条数，则在路径交内。

而有了增删边操作，这个做法肯定是行不通了，因为可能会有若干点对路径在增删边过程中发生了变化。那怎么办呢？

容易得知，如果边 (x, y) 在路径交上，等价于以 x 为树根时，所有路径都恰好有一端点在 y 的子树内。

看到动态换根？考虑 LCT。那怎么判断路径恰好一端在y的子树内？也就是说，如果两端都在也不行，一个端点都没有也不行，这让我们联想到了什么?对，异或！如果我们给每条路径一个数作为它的“特征”，那就可以对每一条路径的两个端点都将其点权异或上其“特征值”，并求 y 子树异或和，如果等于所有路径的异或和，则说明符合条件。

然而不幸的是，这个特征值判断法可能会出错，比如如果有若干条路径权值异或和等于 0 的话，这些路径恰好都不经过所问边时，就会错误地判断。

那怎么办呢？其实只要胆子够大，用随机数就行，把连续几个 rand() 乘起来达到 unsigned long long 数量级（其实远不用这么大），出错率就已经很小了。（当然你要还是不放心再写个线性基判断也行……）

这样，问题就圆满解决啦。

代码：

#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define get(x) (rs(f[x])==x)
#define prf(x) (x&&ch[f[x]][get(x)]==x)
using namespace std;
typedef unsigned long long ull;
inline void read(int& x){
    char c=getchar();x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); 
}
const int N=1e5+5, M=3e5+5;
int n, m, cnt, X[M], Y[M], W[M];
int f[N], ch[N][2], rev[N];
ull val[N], s[N], si[N], cur;
inline void upd(int x){
    s[x]=s[ls(x)]^s[rs(x)]^si[x]^val[x];
}
inline void Rev(int x){
    if(!x) return;
    swap(ls(x), rs(x));
    rev[x]^=1;
}
inline void down(int x){
    if(!rev[x]) return;
    Rev(ls(x)), Rev(rs(x));
    rev[x]=0;
}
inline void all_down(int x){
    if(prf(x)) all_down(f[x]);
    down(x);
}
inline void rot(int x){
    int y=f[x], z=f[y], d=get(x), son=ch[x][!d];
    if(prf(y)) ch[z][get(y)]=x; f[x]=z;
    ch[x][!d]=y; f[y]=x;
    ch[y][d]=son; if(son) f[son]=y;
    upd(y), upd(x);
}
inline void splay(int x){
    all_down(x);
    for(int y=f[x]; prf(x); rot(x), y=f[x])
        if(prf(y)) rot(get(x)^get(y)?x:y);
}
inline void access(int x){
    for(int y=0; x; x=f[y=x]){
        splay(x);
        si[x]^=s[rs(x)]^s[y];
        rs(x)=y;
        upd(x);
    }
}
inline void make_rt(int x){
    access(x);
    splay(x);
    Rev(x);
}
inline void split(int x, int y){
    make_rt(x);
    access(y);
    splay(y);
}
inline void link(int x, int y){
    split(x, y);
    f[x]=y;
    si[y]^=s[x];
    upd(y);
}
inline void cut(int x, int y){
    split(x, y);
    f[x]=ls(y)=0;
    upd(y);
}
inline void modify(int x, int v){
    access(x);
    splay(x);
    val[x]^=v;
    upd(x);
}
inline ull query(int x, int y){
    split(x, y);
    return si[y]^val[y];
}
int main(){
    read(n);
    read(n);read(m);
    for(int i=1, x, y; i<n; ++i){
        read(x);read(y);
        link(x, y);
    }
    while(m--){
        int opt, x, y;
        read(opt);
        switch(opt){
            case 1:
                read(x);read(y);
                cut(x, y);
                read(x);read(y);
                link(x, y);
                break;
            case 2:
                ++cnt;
                read(X[cnt]);read(Y[cnt]);
                W[cnt]=rand()*rand()*rand()*rand()*rand();
                modify(X[cnt], W[cnt]);
                modify(Y[cnt], W[cnt]);
                cur^=W[cnt];
                break;
            case 3:
                read(x);
                modify(X[x], W[x]);
                modify(Y[x], W[x]);
                cur^=W[x];
                break;
            case 4:
                read(x);read(y);
                puts(query(x, y)^cur?"NO":"YES");
                break;
        }
    }
    return 0;
}

LCT 与 SAM

啥？这两个玩意儿还能扯到一起？

请看这题：P5212 SubString

要求支持在线在当前串后面插入一个字符串，或者求所给串在当前字符串中的出现次数。

看到对于子串的各种处理就想到 SAM，插入操作不说了，出现次数就是这个串在 SAM 上的匹配节点的 endpos 大小。也就是说要动态维护 endpos 集合大小。

节点 u 的 endpos 集合大小等于其所有子节点的 endpos 集合大小之和，但是 LCT 维护子树和终归不太方便，转化成链加求点权就好了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+5, SZ=26;
inline void decode(char *s, int len, int mask){
    for(int j=0; j<len; ++j){
        mask=(mask*131+j)%len;
        swap(s[j+1], s[mask+1]);
    }
}
int m, n, ans, mask=0;
char s[N], op[10];
namespace LCT{
    #define ls(x) ch[x][0]
    #define rs(x) ch[x][1]
    int f[N], val[N], ch[N][2], stk[N], add[N], rev[N];
    inline bool prefer(int x){
        return x&&(ls(f[x])==x||rs(f[x])==x);
    }
    inline bool get(int x){
        return ls(f[x])^x;
    }
    inline void Rev(int x){
        if(!x) return;
        rev[x]^=1;
        swap(ls(x), rs(x));
    }
    inline void Add(int x, int y){
        if(!x) return;
        add[x]+=y;
        val[x]+=y;
    }
    inline void pushdown(int x){
        if(rev[x]){
            Rev(ls(x));
            Rev(rs(x));
            rev[x]=0;
        }
        if(add[x]){
            Add(ls(x), add[x]);
            Add(rs(x), add[x]);
            add[x]=0;
        }
    }
    inline void rotate(int x){
        int y=f[x], z=f[y], d=get(x), son=ch[x][!d];
        if(prefer(y)) ch[z][get(y)]=x; f[x]=z;
        ch[x][!d]=y; f[y]=x;
        ch[y][d]=son; if(son) f[son]=y;
    }
    inline void splay(int x){
        int y=x, tp=0;
        stk[++tp]=y;
        while(prefer(y)) stk[++tp]=(y=f[y]);
        while(tp) pushdown(stk[tp--]);
        for(y=f[x]; prefer(x); rotate(x), y=f[x])
            if(prefer(y)) rotate(get(y)^get(x)?x:y);
    }
    inline void access(int x){
        for(int y=0; x; x=f[y=x])
            splay(x), rs(x)=y;
    }
    inline void makeroot(int x){
        access(x);
        splay(x);
        Rev(x);
    }
    inline void split(int x, int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    inline void link(int x, int y){
        f[y]=x;
    }
    inline void cut(int x, int y){
        split(x, y);
        f[x]=ls(y)=0;
    }
    inline void modify(int x){
        split(1, x);
        Add(x, 1);
    }
    inline int ask(int x){
        if(!x) return 0;
        splay(x);
        return val[x];
    }
}
namespace SAM{
    int tot=1, las=1, fa[N], ch[N][SZ], len[N];
    inline void ins(int c){
        if(c<0) exit(0);
        if(tot>=N-5) exit(0);
        int p=las, np;
        np=las=++tot;
        len[np]=len[p]+1;
        for(; p&&!ch[p][c]; p=fa[p])
            ch[p][c]=np;
        if(!p) fa[np]=1;
        else{
            int q=ch[p][c];
            if(len[q]==len[p]+1) fa[np]=q;
            else{
                int nq=++tot;
                memcpy(ch[nq], ch[q], sizeof(ch[q]));
                fa[nq]=fa[q];
                LCT::link(fa[nq], nq);
                LCT::val[nq]=LCT::ask(q);
                len[nq]=len[p]+1;
                LCT::cut(fa[q], q);
                fa[np]=fa[q]=nq;
                LCT::link(nq, q);
                for(; p&&ch[p][c]==q; p=fa[p])
                    ch[p][c]=nq;
            }
        }
        LCT::link(fa[np], np);
        LCT::modify(np);
    }
    inline int match(char *s, int n){
        int u=1;
        for(int i=1; i<=n&&u; ++i)
            u=ch[u][s[i]-'A'];
        return u;
    }
}
int main(){
    scanf("%d", &m);
    scanf("%s", s+1);
    n=strlen(s+1);
    for(int i=1; i<=n; ++i)
        SAM::ins(s[i]-'A');
    while(m--){
        scanf("%s%s", op+1, s+1);
        n=strlen(s+1);
        decode(s, n, mask);
        if(op[1]=='A') for(int i=1; i<=n; ++i)
            SAM::ins(s[i]-'A');
        else{
            ans=LCT::ask(SAM::match(s, n));
            printf("%d\n", ans);
            mask^=ans;
        }
    }
    return 0;
}

LCT与动态DP

模板题：P4719 【模板】"动态 DP"&动态树分治

这个很套路了，广义矩阵乘法套上 LCT 来维护就好了（全局平衡二叉树我是不会写的……）。

代码：

#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define prefer(x) (x&&(ls(f[x])==x||rs(f[x])==x))
#define get(x) (rs(f[x])==x)
#define max(x, y) (x>y?x:y)
using namespace std;
const int N=1e5+5, inf=0x3f3f3f3f;
int n, m, a[N], x, y, f[N], ch[N][2], dp[N][2];
vector <int> edge[N];
struct Mtx{
    int dt[2][2];
    inline Mtx(){
        memset(dt, -0x3f, sizeof(dt));
    }
    inline Mtx(int g0, int g1){
        dt[0][0]=dt[0][1]=g0;
        dt[1][0]=g1;
        dt[1][1]=-inf;
    }
    inline Mtx operator*(const Mtx &a)const{
        Mtx b;
        for(int i=0; i<2; ++i)
            for(int j=0; j<2; ++j)
                for(int k=0; k<2; ++k)
                    b.dt[i][j]=max(b.dt[i][j], dt[i][k]+a.dt[k][j]);
        return b;
    }
}val[N], M[N];
inline void dfs(int u, int fa){
    f[u]=fa;
    dp[u][1]=a[u];
    for(int v: edge[u]) if(v!=fa){
        dfs(v, u);
        dp[u][0]+=max(dp[v][1], dp[v][0]);
        dp[u][1]+=dp[v][0];
    }
    M[u]=val[u]=Mtx(dp[u][0], dp[u][1]);
}
inline void update(int x){
    M[x]=val[x];
    if(ls(x)) M[x]=M[ls(x)]*M[x];
    if(rs(x)) M[x]=M[x]*M[rs(x)];
}
inline void rot(int x){
    int y=f[x], z=f[y], d=get(x), v=ch[x][!d];
    if(prefer(y)) ch[z][get(y)]=x; f[x]=z;
    ch[x][!d]=y; f[y]=x;
    ch[y][d]=v; if(v) f[v]=y;
    update(y); update(x);
}
inline void splay(int x){
    for(int y=f[x]; prefer(x); rot(x), y=f[x])
        if(prefer(y)) rot(get(y)^get(x)?x:y);
}
inline void access(int x){
    for(int y=0; x; x=f[y=x]){
        splay(x);
        int g0=val[x].dt[0][0], g1=val[x].dt[1][0];
        if(rs(x)){
            g0+=max(M[rs(x)].dt[0][0], M[rs(x)].dt[1][0]);
            g1+=M[rs(x)].dt[0][0];
        }
        if((rs(x)=y)){
            g0-=max(M[y].dt[0][0], M[y].dt[1][0]);
            g1-=M[y].dt[0][0];
        }
        val[x]=Mtx(g0, g1);
        update(x);
    }
}
inline int work(int x, int y){
    access(x);
    splay(x);
    val[x].dt[1][0]+=y-a[x];
    a[x]=y;
    update(x);
    splay(1);
    return max(M[1].dt[0][0], M[1].dt[1][0]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        scanf("%d", &a[i]);
    for(int i=1; i<n; ++i){
        scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);   
    }
    dfs(1, 0);
    while(m--){
        scanf("%d%d", &x, &y);
        printf("%d\n", work(x, y));
    }
    return 0;
}