关于Link-Cut-Tree的总结

ajcxsu
ajcxsu 2018年09月30日
  • 60 次阅读

本篇文章不是教程。完全参考:http://www.cnblogs.com/flashhu/p/8324551.html 。若要学习请移步。
大概会持续更新?

核心操作

如同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://acxblog.site/archives/link-cut-tree.html
本文采用 CC BY-NC-SA 3.0 协议进行许可