洛谷 P2147 [SDOI2008]洞穴勘测 题解【LCT】

点击量：416

感觉把lct当可删边的并查集用起来比较舒服好写。双倍经验：洛谷 P3950 部落冲突

目录

题目描述

辉辉热衷于洞穴勘测。

某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由$ n$个洞穴（分别编号为$ 1$到$ n$）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。 洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。

辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：

如果监测到洞穴$ u$和洞穴$ v$之间出现了一条通道，终端机上会显示一条指令Connect u v

如果监测到洞穴$ u$和洞穴$ v$之间的通道被毁，终端机上会显示一条指令Destroy u v

经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。

因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。 然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。

辉辉希望能随时通过终端机发出指令Query u v，向监测仪询问此时洞穴$ u$和洞穴$ v$是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

输入输出格式

输入格式：

第一行为两个正整数$ n$和$ m$，分别表示洞穴的个数和终端机上出现过的指令的个数。以下$ m$行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串$ s$（Connect、Destroy或者Query，区分大小写），之后有两个整数$ u$和$ v$ ($ 1\le u$,$ v\le n$且$ u\ne v$) 分别表示两个洞穴的编号。

输出格式：

对每个Query指令，输出洞穴$ u$和洞穴$ v$是否互相连通：是输出Yes，否则输出No。

输入输出样例

输入样例#1：

200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127

输出样例#1：

No
Yes
No

输入样例#2：

3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3

输出样例#2：

Yes
No

说明

数据说明
$ 10\%$的数据满足$ n≤1000, m≤20000$

$ 20\%$的数据满足$ n≤2000, m≤40000$

$ 30\%$的数据满足$ n≤3000, m≤60000$

$ 40\%$的数据满足$ n≤4000, m≤80000$

$ 50\%$的数据满足$ n≤5000, m≤100000$

$ 60\%$的数据满足$ n≤6000, m≤120000$

$ 70\%$的数据满足$ n≤7000, m≤140000$

$ 80\%$的数据满足$ n≤8000, m≤160000$

$ 90\%$的数据满足$ n≤9000, m≤180000$

$ 100\%$的数据满足$ n≤10000, m≤200000$

保证所有Destroy指令将摧毁的是一条存在的通道

题解：

主要使用了lct中的$ link$和$ cut$功能。虽然$ \sout{split}$也很好写不过这个题保证了加删边合法，不用特别考虑特判了。

判断两个点$ (x,y)$是否在同一棵树上只需要先$ makeroot(x)$，然后找$ getroot(y)$是否等于$ x$就可以了。当成了一个可以删除（不等价于撤销）的时间复杂度为大常数$ O(n\log n)$的并查集。

相当于练了一遍板子吧。

Code:

#include<cstdio>
#include<cstring>
#define ls ch[0][k]
#define rs ch[1][k]
#define which(k) (ch[1][fa[k]]==k)
#define isroot(k) (ch[0][fa[k]]!=k&&ch[1][fa[k]]!=k)
#define maxn 10100
int ch[2][maxn],fa[maxn];
int lazy[maxn];
void pushdown(int k)
{
    if(lazy[k])
    {
        int tmp=ls;
        ls=rs;
        rs=tmp;
        lazy[ls]^=1;
        lazy[rs]^=1;
        lazy[k]=0;
    }
}
void Rotate(int k)
{
    int y=fa[k];
    if(!isroot(y))
        ch[which(y)][fa[y]]=k;
    bool d=which(k);
    fa[k]=fa[y];
    fa[y]=k;
    ch[d][y]=ch[!d][k];
    fa[ch[d][y]]=y;
    ch[!d][k]=y;
}
int stk[10010],tp=0;
void splay(int k)
{
    int x=k;
    while(!isroot(x))
    {
        stk[++tp]=x;
        x=fa[x];
    }
    stk[++tp]=x;
    while(tp)
        pushdown(stk[tp--]);

    while(!isroot(k))
    {
        int y=fa[k];
        if(!isroot(y))
            Rotate(which(k)^which(y)?k:y);
        Rotate(k);
    }
}
void access(int k)
{
    for(int x=k,y=0;x;y=x,x=fa[x])
    {
        splay(x);
        ch[1][x]=y;
        //maintain(x);
    }
}
void makeroot(int k)
{
    access(k);
    splay(k);
    lazy[k]^=1;
}
int getroot(int k)
{
    access(k);
    splay(k);
    while(ls)
        k=ls;
    return k;
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
    fa[x]=ch[0][y]=0;
}
char op[100];
int main()
{
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        scanf("%d%d",&u,&v);
        if(op[0]=='C')
            link(u,v);
        else if(op[0]=='D')
            cut(u,v);
        else
        {
            makeroot(u);
            if(getroot(v)==u)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}