核心操作

如同 splay 和左偏树一样，lct 也有一个属于他的核心操作，即split(x,y)。
代表着将 x 到 y 的这条链剖离出来。由于每条链使用 splay 维护，把这条链剖离出来就达到了获取链上信息的目的。

为了达到split(x,y)这一目的，使用了makeroot(x)、access(x)等形式多样的操作。
为了达到每条链使用 splay 维护的目的，使用了虚实链剖分这一性质。

这就是 lct 这一数据结构的大览。

主要操作

access(x)

生成根到 x 的链的 splay （不保证 x 在此操作后旋到 splay 的根，因此需要手动 splay） 。

makeroot(x)

将 x 作为新树的根。
因为access(x), splay(x)以后 x 深度最深，所以给 x 打上反转标记即可。
即将链的中序遍历反转。

split(x, y)

makeroot(x), access(y), splay(y)，则链的信息被存储在 y 中。

findroot(x)

splay(x)后向左儿子找深度最浅点，记得下放。
最后需要 splay 最浅点以保证势能复杂度分析正确。
（常用于判断连通性）

cut(x, y)

split(x, y)
分类讨论一下可以知道只有在x->f==y && x->ch[1]==nil时 x 与 y 相连（此时 y 为 splay 的根）。
若因为 findroot 而使 x 变为 splay 的根，则条件变为y->ch[0]==nil && y->f==x。

link(x, y)

makeroot(x), x->f=y

Code

// Code by ajcxsu
// Problem: lct

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=3e5+10;
struct Node *nil;
struct Node {
    Node *ch[2], *f;
    int v, sum, s, c;
    char tag;
    Node (int v=0):v(v), sum(v) { tag=0; s=c=1; ch[0]=ch[1]=f=nil; }
    bool nroot() { return f->ch[0]==this || f->ch[1]==this; }
    int dir() { return nroot()?f->ch[1]==this:-1; }
    void pud() { if(tag) swap(ch[0], ch[1]), ch[0]->tag^=1, ch[1]->tag^=1, tag=0; }
    void upd() { sum=v^ch[0]->sum^ch[1]->sum, s=c+ch[0]->s+ch[1]->s; }
} *nd[N], po[N], *pp=po;
void ini() {
    nil=pp++, nil->ch[0]=nil->ch[1]=nil->f=nil;
    nil->s=nil->c=0;
}
void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x, y->upd();
}
Node *stk[N];
void splay(Node *x) {
    Node *y=x; int z=0;
    stk[++z]=y;
    while(y->nroot()) stk[++z]=y=y->f;
    while(z) stk[z--]->pud();
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir()==x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
}

void access(Node *x) {
    Node *y=nil;
    while(x!=nil) splay(x), x->ch[1]=y, x->upd(), y=x, x=x->f;
}
void makeroot(Node *x) {
    access(x), splay(x), x->tag^=1;
}
Node* findroot(Node *x) {
    access(x), splay(x);
    while(x->ch[0]!=nil) x=x->ch[0], x->pud();
    return splay(x), x;
}
void Link(Node *x, Node *y) {
    makeroot(x);
    if(x==findroot(y)) return;
    x->f=y;
}
void split(Node *x, Node *y) { makeroot(x), access(y), splay(y); }
void Cut(Node *x, Node *y) {
    makeroot(x);
    if(findroot(y)==x && y->f==x && y->ch[0]==nil)
        y->f=nil, x->ch[1]=nil, x->upd(); // x为根
}


int main() {
    ini();
    int n, m, na;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) gn(na), nd[i]=pp++, *nd[i]=Node(na);
    int opt, x, y;
    while(m--) {
        gn(opt), gn(x), gn(y);
        if(opt==0) split(nd[x], nd[y]), printf("%d\n", nd[y]->sum);
        else if(opt==1) Link(nd[x], nd[y]);
        else if(opt==2) Cut(nd[x], nd[y]);
        else if(opt==3) makeroot(nd[x]), nd[x]->v=y, nd[x]->upd();
    }
    return 0;
}

注意事项

所有对于 splay 单个节点的数据更改（比如需要改某点的虚子树值，题目的单点修改操作），应当先将被操作的节点旋至所属 splay 的根节点。否则由于 upd 不及时，splay 的数据维护将出现问题。

对子树的维护（维护虚子树的权值和）

lct 一般用于对链进行维护。对链 + 子树的维护一般用树剖。但有些题加入了增删边的操作，强制让我们使用 lct 进行维护。
一般来说这类题目对于子树的维护都是 大小、权值和 之类的。
我们无法统计子树和的原因是由于 lct 认父不认子 的性质，导致我们无法加上虚边连接的子树的权值之和。
所以我们可以对每个点增加一个虚子树权值之和，代表每个指向该点的虚边的来源 splay 的权值之和。然后就可以达到维护子树的目的。

比如我们要动态维护子树的大小。
假设某个链的子树大小为 s。
然后这条链所代表的 splay 顶端有一条虚边指向了一个点 i。
我们让 i 里的虚子树权值 si 加上这个 s。
然后 i 所在的 splay 统计它自己所代表链的子树大小和，就会带上这个虚子树，破除 lct 认父不认子的性质。

对双连通分量的维护

当我们需要对树上双连通分量（点双）进行动态出现的维护（也就是说不包括删除），我们可以这么做：

使用两个并查集。一个并查集维护每个点所属的点双，一个并查集维护他们是否连在同一个树（因为边不会被删除）。

当我们需要在两个不同的点双连边，这两个点双又连在同一棵树上，则我们需要把新出现的环缩点。
因此我们把这条链剖下来，递归处理这棵子树，把这棵子树上的点在第一个并查集上更新其所属的点双。这个点双的代表点就用现在这条链上 splay 的根 $root$。

然后我们把 $root$ 的两个子树置为 nil。

那你说这棵子树上残留的虚边怎么办？
因此，我们 access 往上去找的时候，我们必须找所处点父亲所处的点双的代表节点，并且跳到那里去。
最最重要的是，我们需要把该点的父亲也在此时给更新一下。

因为我们在 access 完之后 splay，在 rotate 时将会直接调用一个点的父亲指针来更新父亲对它的儿子信息，因此 rotate 时每个点的父亲指向必须正确。我们由于只会在 access 过后的 splay 进行 splay 和 rotate 操作，因此只需要在 access 上加入这个代码就行了。

值得注意的是，在 rotate 里即时更新一下父亲指针是不行的。rotate 所能顾及到的情况要比 access 要小得多，并且会多许多冗余的常数。

例题：LP2542 [AHOI2005]航线规划
https://www.luogu.org/problemnew/show/P2542

参考代码：

// Code by ajcxsu
// Problem: flight_planning

#include<bits/stdc++.h>
using namespace std;

void gn(int &x) {
    char ch=getchar();
    int pl=1;
    x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}

const int N=3e4+10, M=1e5+10;
struct Opt {
    int c, a, b, id;
} opt[M];
set<int> to[N];
int cnt,q;
int ans[M];

struct FMT {
    int fa[N];
    FMT() { memset(fa, 0, sizeof(fa)); }
    int Find(int x) {
        if(!fa[x]) return x;
        return fa[x]=Find(fa[x]);
    }
    bool Union(int a, int b) {
        int af=Find(a), bf=Find(b);
        if(af==bf) return false;
        fa[af]=bf;
        return true;
    }
} fm1, fm2;

struct Node *nil;
struct Node {
    int s, c, id;
    bool t;
    Node *f, *ch[2];
    Node(int id=0):id(id) { t=false, s=c=1; f=ch[0]=ch[1]=nil; }
    bool nroot() { return f->ch[0]==this || f->ch[1]==this; }
    int dir() {
        if(!nroot()) return -1;
        return f->ch[1]==this;
    }
    void pud() {
        if(!t) return;
        t=0, ch[0]->t^=1, ch[1]->t^=1, swap(ch[0], ch[1]);
    }
    void upd() {
        s=ch[0]->s+ch[1]->s+c;
    }
} *nd[N];
void ini() {
    nil=new Node;
    nil->f=nil->ch[0]=nil->ch[1]=nil;
    nil->s=nil->c=0;
}

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x;
    y->upd();
}

Node *stk[N];
void splay(Node *x) {
    int z=0;
    Node *y=x;
    stk[++z]=y;
    while(y->nroot()) stk[++z]=y=y->f;
    while(z) stk[z--]->pud();
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir() == x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
}

void access(Node *x) {
    Node *y=nil;
    while(x!=nil) {
        splay(x), x->ch[1]=y, x->upd();
        y=x, y->f=x=nd[fm1.Find(x->f->id)]; // The most important line
    }
}

void makeroot(Node *x) {
    access(x), splay(x), x->t^=1;
}

void split(Node *x, Node *y) {
    makeroot(x), access(y), splay(y);
}
void link(Node *x, Node *y) {
    makeroot(x), x->f=y;
}
void deal(Node *x, int f) {
    if(x==nil) return;
    fm1.Union(x->id, f);
    deal(x->ch[0], f), deal(x->ch[1], f);
}

int main() {
    ini();
    int n,m;
    gn(n), gn(m);
    nd[0]=nil;
    for(int i=1;i<=n;i++) nd[i]=new Node(i);
    int u,v;
    for(int i=1;i<=m;i++) {
        gn(u), gn(v);
        if(u==v) continue;
        if(u>v) swap(u,v);
        to[u].insert(v);
    }
    int c,a,b;
    while(gn(c), c!=-1) {
        gn(a), gn(b);
        if(a>b) swap(a,b);
        opt[++cnt]={c,a,b};
        if(c==1) opt[cnt].id=++q;
        else to[a].erase(to[a].find(b));
    }
    for(int i=1;i<=n;i++)
    for(set<int>::iterator it=to[i].begin();it!=to[i].end();it++) {
        a=fm1.Find(i), b=fm1.Find(*it);
        if(a==b) continue;
        if(!fm2.Union(a,b)) {
            split(nd[a], nd[b]);
            deal(nd[b], b);
            nd[b]->ch[0]=nd[b]->ch[1]=nil;
            nd[b]->upd();
        }
        else link(nd[a], nd[b]);
    }
    for(int i=cnt;i>=1;i--) {
        c=opt[i].c, a=opt[i].a, b=opt[i].b;
        if(c==1) {
            a=fm1.Find(a), b=fm1.Find(b);
            split(nd[a], nd[b]);
            ans[opt[i].id]=nd[b]->s-1;
        }
        else {
            a=fm1.Find(a), b=fm1.Find(b);
            if(a!=b) {
                split(nd[a], nd[b]);
                deal(nd[b], b);
                nd[b]->ch[0]=nd[b]->ch[1]=nil;
                nd[b]->upd();
            }
        }
    }
    for(int i=1;i<=q;i++) printf("%d\n", ans[i]);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/link-cut-tree.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议进行许可☆

昵称*

邮箱*

网站

加入讨论吧...