【洛谷3950】部落冲突（LCT维护连通性）

点此看题面

大致题意： 给你一棵树，\(3\)种操作：连一条边，删一条边，询问两点是否联通。

\(LCT\)维护连通性

有一道类似的题目：【BZOJ2049】[SDOI2008] Cave 洞穴勘测。

这两道题都是\(LCT\)动态维护连通性的模板题。

考虑将\(x\)和\(y\)连边时，我们就在\(LCT\)上\(Link(x,y)\)。

同理，\(x\)和\(y\)断边时，就\(Cut(x,y)\)。

询问连通性时，只要判断\(FindRoot(x)\)与\(FindRoot(y)\)是否相等即可。

代码

#include<bits/stdc++.h>

#define N 300000

#define swap(x,y) (x^=y^=x^=y)

using namespace std;

int n,u[N+5],v[N+5];

class Class_FIO

{

    private:

        #define Fsize 100000

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)

        char ch,*A,*B,Fin[Fsize];

    public:

        Class_FIO() {A=B=Fin;}

        inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}

        inline void readc(char &x) {while(isspace(x=tc()));}

}F;

class Class_LCT//LCT模板

{

    private:

        #define LCT_SIZE N

        #define Rever(x) (swap(node[x].Son[0],node[x].Son[1]),node[x].Rev^=1)

        #define PushDown(x) (node[x].Rev&&(Rever(node[x].Son[0]),Rever(node[x].Son[1]),node[x].Rev=0))

        #define Which(x) (node[node[x].Father].Son[1]==x)

        #define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)

        #define IsRoot(x) (node[node[x].Father].Son[0]^x&&node[node[x].Father].Son[1]^x)

        #define MakeRoot(x) (Access(x),Splay(x),Rever(x))

        int Stack[LCT_SIZE+5];

        struct Tree

        {

            int Father,Rev,Son[2];

        }node[LCT_SIZE+5];

        inline void Rotate(int x)

        {

            register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);

            !IsRoot(fa)&&(node[pa].Son[Which(fa)]=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1);

        }

        inline void Splay(int x)

        {

            register int fa=x,Top=0;

            while(Stack[++Top]=fa,!IsRoot(fa)) fa=node[fa].Father;

            while(Top) PushDown(Stack[Top]),--Top;

            while(!IsRoot(x)) fa=node[x].Father,!IsRoot(fa)&&(Rotate(Which(x)^Which(fa)?x:fa),0),Rotate(x);

        }

        inline void Access(int x) {for(register int son=0;x;x=node[son=x].Father) Splay(x),node[x].Son[1]=son;}

        inline int FindRoot(int x) {Access(x),Splay(x);while(node[x].Son[0]) PushDown(x),x=node[x].Son[0];return Splay(x),x;}

    public:

        inline void Link(int x,int y) {MakeRoot(x),FindRoot(y)^x&&(node[x].Father=y);}

        inline void Cut(int x,int y) {MakeRoot(x),!(FindRoot(y)^x)&&!(node[y].Father^x)&&!node[y].Son[0]&&(node[y].Father=node[x].Son[1]=0);}

        inline bool IsConnected(int x,int y) {return !(FindRoot(x)^FindRoot(y));}//判断连通性

}LCT;

int main()

{

    register int query_tot,i,x,y,cnt=0;register char op;

    for(F.read(n),F.read(query_tot),i=1;i<n;++i) F.read(x),F.read(y),LCT.Link(x,y);

    while(query_tot--)

    {

        F.readc(op);switch(op)

        {

            case 'C':F.read(u[++cnt]),F.read(v[cnt]),LCT.Cut(u[cnt],v[cnt]);break;//连边

            case 'U':F.read(x),LCT.Link(u[x],v[x]);break;//删边

            case 'Q':F.read(x),F.read(y),puts(LCT.IsConnected(x,y)?"Yes":"No");break;//询问

        }

    }

    return 0;

}