BruceJay's Blog

BZOJ2049 洞穴勘测

| Comments

To start with

LCT模板题。。。

Bruce正在LCT中挣扎。。。。

Problem

Solution

在此还是有必要简述一下link-cut tree。
LCT支持树的合并(link),切分(cut),以及对链的一些操作。大体思想与树链剖分中的轻重链类似,只是重链会发生一些改变,所以需要结合Splay灵活维护。
与树剖的重链类似,LCT也有Preferred的定义。
Preferred child:如果当前被访问的节点在X的P儿子所在的子树中,则称P是X的Preferred Child。
Preferred edge:如上,P与X的连边便是X的Preferred edge。
Preferred path:由连续一段Preferred edge组成的不可延伸的路径。
为了维护链上信息,我们就可以将一条Preferred edge上所有的点以深度为关键字建立Splay进行维护。
LCT支持一下操作:

Access(x)

LCT最基本的操作,根据对Preferred path的定义,如果x被访问,那么x到根的路径上所有的边都会变为Preferred edge,而x到根的路径上每个点与原来的Preferred child之间的Preferred edge将会被断开。
所以在将边(x,fa[x])变成Preferred edge的操作中,将fa[x]旋转到其所在Splay树上的根节点,将其与其右子树断开,将其右儿子变成u。

void Access(int x)
{
    int t=0;
    for(;x;x=fa[x]){
        Splay(x);
        rt[tr[x][1]]=true;
        tr[x][1]=t; rt[t]=false;
        t=x;
    }
}

Reverse(x)

将u旋转到所在树的根节点的操作,先Access(x),直接将x到根的翻转一些即可,相当于在Splay树上打个reverse标记。

void Reverse(int x)
{
    Access(x); Splay(x); rev[x]^=1;
}

Link(u,v)

将v转到所在树的根节点,Access(u)一下,同时可以将u和v所在的Splay合并。

void Link(int u,int v)
{
    Reverse(v); Access(u); Splay(u);
    tr[u][1]=v; rt[v]=false; fa[v]=u;
    Pushup(u);
}

Cut(u,v)

将v转到根,Access(u)一下,这条Preferred path只含一条Preferred edge--(u,v)了,在Splay上将u和v断开。

void Cut(int u,int v)
{
    Reverse(v); Access(u); Splay(u);
    rt[v]=true; tr[u][0]=fa[v]=0;
    Pushup(u);
}

这题多了一个询问是否联通的操作,就是找所在树的根节点,只需分别Access(u),Access(v),然后找到所在Splay上最靠左的节点。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10100;
int fa[N]; int tr[N][2];
int sz[N]; bool rev[N];
int st[N]; bool rt[N];
int n,m;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Pushdown(int x)
{
    int l=tr[x][0],r=tr[x][1];
    if(rev[x]){
        rev[x]^=1; rev[l]^=1; rev[r]^=1;
        swap(tr[x][0],tr[x][1]);
    }
}

void Rotate(int x)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(rt[y]) rt[y]=false,rt[x]=true;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
}

void Splay(int x)
{
    int top=0; st[++top]=x;
    for(int i=x;i;i=fa[i]) st[++top]=fa[i];
    for(int i=top;i;i--) Pushdown(st[i]);
    while(!rt[x]){
        int y=fa[x];
        if(!rt[y]){
            int z=fa[y];
            if(tr[z][0]==y^tr[y][0]==x) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
}

void Access(int x)
{
    int t=0;
    for(;x;x=fa[x]){
        Splay(x);
        rt[tr[x][1]]=true;
        tr[x][1]=t; rt[t]=false;
        t=x;
    }
}

void Reverse(int x)
{
    Access(x); Splay(x); rev[x]^=1;
}

void Link(int x,int y)
{
    Reverse(x); Access(y);
    fa[x]=y; Splay(x);
}

void Cut(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    tr[y][0]=fa[x]=0; rt[x]=true;
}

int Find(int x)
{
    Access(x); Splay(x);
    int y=x;
    while(tr[y][0]) y=tr[y][0];
    return y;
}

int main()
{
    char s[10]; int u,v;
    freopen("2049.in","r",stdin);
    freopen("2049.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++) rt[i]=true,sz[i]=1;
    for(int i=1;i<=m;i++){
        scanf("%s",s); u=read(); v=read();
        if(s[0]=='C') Link(u,v);
        else if(s[0]=='D') Cut(u,v);
        else{
            if(Find(u)==Find(v)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

Last but not least

半年前看LCT毛都不会,现在居然硬着头皮看懂了那么一丢丢。

Comments

comments powered by Disqus