因为BZOJ挂了,我是在lg上交的

感谢waltz719提供的讲义;感谢wxd,zxx老师提供的书籍

效率还行..?

测试点 #1：通过该测试点。 得分10，耗时31ms，内存2113kB。
测试点 #2：通过该测试点。 得分10，耗时62ms，内存2134kB。
测试点 #3：通过该测试点。 得分10，耗时109ms，内存2158kB。
测试点 #4：通过该测试点。 得分10，耗时156ms，内存2183kB。
测试点 #5：通过该测试点。 得分10，耗时171ms，内存2211kB。
测试点 #6：通过该测试点。 得分10，耗时234ms，内存2236kB。
测试点 #7：通过该测试点。 得分10，耗时249ms，内存2252kB。
测试点 #8：通过该测试点。 得分10，耗时280ms，内存2285kB。
测试点 #9：通过该测试点。 得分10，耗时327ms，内存2310kB。
测试点 #10：通过该测试点。 得分10，耗时358ms，内存2322kB。

题目是中文的不需要翻译

题目链接:

http://www.luogu.org/problem/show?pid=2147

http://dev.luogu.org:3308/problem/show?pid=2147

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

题解:

用一颗LCT维护!

其实我想写的是LCT怎么去维护的

LCT分为好几个操作

1,splay 这个..跟平衡树里的splay操作一样,就是把某个点转到根

2,access 这个是一个核心步骤

首先LCT需要的是一颗二叉排序树

那么..还是看图好了..

access就是这么做的呢 不过access到顶以后要把N-O这一条边去掉

access因为受到后面evert函数里增加的翻转因素的影响,需要对x的father先splay一遍,之前没写..实际上这是个非常重要的步骤

3,evert

先用access把x弄到整个树的树根

然后开个rev的开关即可..

因为它的右子树被断开,左子树(即它的祖先)被它翻转到右子树,所以x就是根了

4,link

evert(x); x->father=y;

似乎没啥多说的

4,cut

evert(x); access(y);这样x一定是y的左子树 断开这条边即可

y->ch[0]->father = null; y->ch[0] = null;

5,findroot

access(x); 一直向左走走到尽头

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int id;
    bool rev;
    node * ch[2];
    node * father;
};
node * a[10005];
node * null;
node * new_node(int x)
{
    static node a[20005];
    static int top=0;
    node * t=&a[top++];
    t->ch[0]=null;
    t->ch[1]=null;
    t->father=null;
    t->id=x;
    return t;
}
int get_up(node * x)
{
    node * y=x->father;
    if (y->ch[0]==x) return 0;
    if (y->ch[1]==x) return 1;
    return -1;
}
void update(node * x)
{
    if (x->rev)
    {
        swap(x->ch[0],x->ch[1]);
        x->rev=false;
        x->ch[0]->rev^=1;
        x->ch[1]->rev^=1;
    }
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->father=x->father;
    x->father=y;
    x=y;
}
void splay(node * &x)
{
    for (;;)
    {
        update(x->father->father);
        update(x->father);
        update(x);
        int t1=get_up(x);
        if (t1==-1) return;
        int t2=get_up(x->father);
        if (t2==-1)
        {
            x=x->father;
            rotate(x,t1);
        }
        else
        {
            int t3=get_up(x->father->father);
            if (t3==-1)
            {
                if (t1==t2)
                {
                    x=x->father;
                    x=x->father;
                    rotate(x,t2);
                    rotate(x,t1);
                }
                else
                {
                    x=x->father;
                    x=x->father;
                    rotate(x->ch[t2],t1);
                    rotate(x,t2);
                }
            }
            else
            {
                if (t1==t2)
                {
                    x=x->father;
                    x=x->father;
                    x=x->father;
                    rotate(x->ch[t3],t2);
                    rotate(x->ch[t3],t1);
                    x=x->ch[t3];
                }
                else
                {
                    x=x->father;
                    x=x->father;
                    rotate(x->ch[t2],t1);
                    x=x->father;
                    rotate(x->ch[t3],t2);
                    x=x->ch[t3];
                }
            }
        }
    }
}
void access(node * &x)
{
    for (;;)
    {
        splay(x);
        if (x->father==null)
        {
            x->ch[1]=null;
            return;
        }
        splay(x->father);
        x->father->ch[1]=x;
    }
}
void evert(node * x)
{
    access(x);
    x->rev^=1;
}
void link(node * x,node * y)
{
    evert(x);
    x->father=y;
}
void cut(node * x,node * y)
{
    evert(x);
    access(y);
    y->ch[0]->father=null;
    y->ch[0]=null;
}
int findroot(node * x)
{
    access(x);
    node * t=x;
    for (;;)
    {
        if (t->ch[0]==null) return t->id;
        t=t->ch[0];
        update(t);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    null=new_node(-1);
    null->ch[0]=null;
    null->ch[1]=null;
    null->father=null;
    for (i=0;i<n;i++)
    {
        a[i]=new_node(i);
    }
    for (i=0;i<m;i++)
    {
        static char c[105];
        scanf("%s",c);
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        if (c[0]=='Q')
        {
            if ((findroot(a[x])==findroot(a[y])))
            {
                puts("Yes");
            }
            else
            {
                puts("No");
            }
        }
        else if (c[0]=='D')
        {
            cut(a[x],a[y]);
        }
        else
        {
            link(a[x],a[y]);
        }
    }
    return 0;
}