首页 > 代码库 > 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;}
BZOJ2049 SDOI2008 洞穴勘测 LCT
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。