首页 > 代码库 > BZOJ2049 SDOI2008 洞穴勘测 LCT

BZOJ2049 SDOI2008 洞穴勘测 LCT

题意:给定一棵树,维护:1、删除一条边  2、添加一条边  3、询问u和v是否连通

题解:LCT维护连通性

技术分享
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=10000+2;typedef struct NODE{    NODE *child[2],*f;    bool rev;} *TREE;TREE root,Null,mark[MAXN];int N,M;char s[10];TREE NewNode(TREE f){    TREE x=new NODE;    x->f=f,x->child[0]=x->child[1]=Null;    x->rev=0;    return x;}void Initialize(int N){    Null=NewNode(0);    for(int i=1;i<=N;i++) mark[i]=NewNode(Null);}void Pushdown(TREE &x){    if(x->f->child[0]==x || x->f->child[1]==x) Pushdown(x->f);    if(x->rev){        swap(x->child[0],x->child[1]);        x->child[0]->rev^=1,x->child[1]->rev^=1;        x->rev=0;    }}void Rotate(TREE &x,bool t){    TREE y=x->f;    y->child[!t]=x->child[t],x->child[t]->f=y,x->f=y->f;    if(y->f->child[0]==y) y->f->child[0]=x;    if(y->f->child[1]==y) y->f->child[1]=x;    x->child[t]=y,y->f=x;}void Splay(TREE &x){    Pushdown(x);    TREE y=x->f;    while(y->child[0]==x || y->child[1]==x){        if(y->child[0]==x){            if(y->f->child[0]==y) Rotate(y,1);            Rotate(x,1);        }        else{            if(y->f->child[1]==y) Rotate(y,0);            Rotate(x,0);        }        y=x->f;    }}void Access(TREE &x){    TREE y=Null,z=x;    while(z!=Null){        Splay(z);        z->child[1]=y;        y=z,z=z->f;    }}void Move(TREE &x){    Access(x),Splay(x);    x->rev^=1,Pushdown(x);}void Link(TREE &x,TREE &y){    Move(x);    x->child[0]=Null,x->f=y;}void Cut(TREE &x,TREE &y){    Move(x);    x->child[1]=Null;    Access(y);    x->child[1]=Null;    Splay(y);    y->f=Null;}TREE Query(TREE &x){    TREE y=x;    while(y->f!=Null) y=y->f;    return y;}int main(){    scanf("%d %d",&N,&M);    Initialize(N);    for(int i=1,x,y;i<=M;i++){        scanf("%s %d %d",s,&x,&y);        if(s[0]==Q)            if(Query(mark[x])==Query(mark[y])) puts("Yes");            else puts("No");        if(s[0]==C) Link(mark[x],mark[y]);        if(s[0]==D) Cut(mark[x],mark[y]);    }    return 0;}
View Code

 

BZOJ2049 SDOI2008 洞穴勘测 LCT