也还是挺好写的

    #define NN 100001
    struct inf{int ch[2],r,p;bool rev;}t[NN];
    inline bool isroot(int o)
    {return o==0||(t[t[o].p].ch[0]!=o&&t[t[o].p].ch[1]!=o);}
    inline void pushdown(int o)
    {
        int lc=t[o].ch[0],rc=t[o].ch[1];
        if(t[o].rev)
        {
            int tmp=t[o].ch[0];
            t[o].ch[0]=t[o].ch[1];
            t[o].ch[1]=tmp;
            t[lc].rev^=1;t[lc].r^=1;
            t[rc].rev^=1;t[rc].r^=1;
            t[o].rev=false;
        }
    }
    void pushup(int o)
    {

    }
    inline void setc(int f,int c,int sty)
    {t[f].ch[sty]=c;t[c].p=f;t[c].r=sty;pushup(f);}
    inline void rotate(int o,int sty)
    {
        int x=t[o].ch[sty];
        if(isroot(o))t[x].p=t[o].p;
        else setc(t[o].p,x,t[o].r);
        setc(o,t[x].ch[1^sty],sty);
        setc(x,o,1^sty);
    }
    int stack[NN],top;
    void splay(int o)
    {
        stack[top=1]=o;
        int x=o,y;
        while(!isroot(x)){stack[++top]=t[x].p;x=t[x].p;}
        while(top)pushdown(stack[top--]);
        while(!isroot(o))
        {
            x=t[o].p;y=t[x].p;
            if(isroot(x))
                rotate(x,t[o].r);
            else
            {
                if(t[o].r==t[x].r)
                    rotate(y,t[x].r);
                rotate(x,t[o].r);
            }
        }
    }

void access(int o)
{
	int tmp=0;
	while(o)
	{
		splay(o);
		setc(tmp,o,1);
		tmp=o;
		o=t[o].p;
	}
}

int getroot(int o)
{
	access(o);
	splay(o);
	while(t[o].ch[0])o=t[o].ch[0];
	return o;
}

void setroot(int o)
{
	access(o);
	splay(o);
	t[o].rev^=1;
}

void link(int u,int v)
{
	if(getroot(u)==getroot(v))return;
	setroot(u);
	t[u].p=v;
}

void destory(int u,int v)
{
	access(u);
	splay(v);
	if(t[v].p==u)t[v].p=0;
	else
	{
		access(v);
		splay(u);
		if(t[u].p==v)t[u].p=0;
	}
}