bzoj 2049 [Sdoi2008]Cave 洞穴勘测（LCT）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=2049

【题意】

给定森林，可能有连边或断边的操作，回答若干个连通性的询问。

【思路】

Link-Cut-Tree。

LCT的性质：

　　1．有一条重链上的所有节点构成的splay称作这条链的辅助树。

　　2．每个点的键值为这个点的深度。

　　3．链的辅助树的根的父亲指向链顶的父亲，然而链顶父亲的儿子并不指向链的辅助树的根。

　 (我会告诉你上面是抄的Popoqqq大爷的PPT么

LCT的操作:

Access：切断原来的重儿子，将结点到原树根的路径变为重路径。先splay到辅助树的根，然后修改右儿子，只用修改ch[1]，右儿子的fa不用改变。

Evert：将u旋转至原树的根，因为执行完Access之后u只是辅助树的根，所以还需要splay至原树根。维护2性质，通过旋转之后u到根的路径反转，需要打上反转标记。

Link：连接两个不相连的节点。将u旋转至原树的根，然后将u的fa设为v。注意这里的操作并不是合并splay而只是连接两棵辅助树。

Cut：断开两个节点。将u旋转至跟，然后Access(v),splay(v)，这时候u一定处于v的左子树，直接切断就行了。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<iostream>

 using namespace std;

 const int N = 1e5+;

 struct Node {

     Node *ch[],*fa;

     int rev;

     Node() ;

     void reverse() {

         rev^=;

         swap(ch[],ch[]);

     }

     void up_push() {

         if(fa->ch[]==this||fa->ch[]==this)

             fa->up_push();

         if(rev) {

             ch[]->reverse();

             ch[]->reverse();

             rev=;

         }

     }

     void maintain() {

     }

 };

 Node *null=new Node,T[N];

 Node::Node() { fa=ch[]=ch[]=null; rev=; }

 void rot(Node* o,int d) {                        //将o点向上旋转,方向为d^1

     Node *p=o->fa;

     p->ch[d]=o->ch[d^];

     o->ch[d^]->fa=p;

     o->ch[d^]=p;

     o->fa=p->fa;

     if(p==p->fa->ch[])

         p->fa->ch[]=o;

     else if(p==p->fa->ch[])

         p->fa->ch[]=o;

     p->fa=o;

     p->maintain();

 }

 void splay(Node* o) {                            //自下向上旋转至[所属splay]的根

     o->up_push();

     Node *nf,*nff;

     while(o->fa->ch[]==o||o->fa->ch[]==o) {    //判断是否是根

         nf=o->fa,nff=nf->fa;

         if(o==nf->ch[]) {

             if(nf==nff->ch[]) rot(nf,);

             rot(o,);

         } else {

             if(nf==nff->ch[]) rot(nf,);

             rot(o,);

         }

     }

     o->maintain();

 }

 void Access(Node* o) {

     Node* son=null;

     while(o!=null) {                            //将o到根的路径变为重路径即合并到一棵splay

         splay(o);

         o->ch[]=son;

         o->maintain();

         son=o; o=o->fa;

     }

 }

 void evert(Node* o) {                            //将o转到[整棵动态树]的根

     Access(o);

     splay(o);

     o->reverse();

 }

 void Link(Node* u,Node* v) {

     evert(u);

     u->fa=v;                                    //辅助树的根指向链顶的父亲然而链顶的父亲并不指向根

 }

 void Cut(Node* u,Node* v) {

     evert(u);

     Access(v),splay(v);

     v->ch[]=u->fa=null;

     v->maintain();

 }

 int n,m;

 void query(Node* u,Node* v)

 {

     Access(u),splay(u);

     while(v->fa!=null) v=v->fa;

     if(u==v) puts("Yes");

     else puts("No");

 }

 int main()

 {

    // freopen("in.in","r",stdin);

    // freopen("out.out","w",stdout);

     null->fa=null->ch[]=null->ch[]=null;

     char op[]; int u,v;

     scanf("%d%d",&n,&m);

     while(m--) {

         scanf("%s%d%d",&op,&u,&v);

         if(op[]=='Q')

             query(&T[u],&T[v]);

         else if(op[]=='C')

             Link(&T[u],&T[v]);

         else

             Cut(&T[u],&T[v]);

     }

     return ;

 }

巴特西

bzoj 2049 [Sdoi2008]Cave 洞穴勘测（LCT）

最新文章

热门文章