BZOJ-3282: Tree

Description

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

裸LCT求点权亦或。在下传标记的时候居然条件写成了x!=null，无限TLE。被自己蠢哭（注：应当只在当前splay树上pushdown，所以应该是isroot）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    node *fa,*c[2];
    int tur,w,sum;
    node(int x);
    void reverse();
    void pushup();
    void pushdown();
}*null=new node(0),*t[301000];
node::node(int x)
{
    fa=c[0]=c[1]=null;
    tur=0; w=sum=x;
}
void node::reverse()
{
    if(this==null) return ;
    swap(c[0],c[1]); tur^=1;
}
void node::pushup() {sum=w^c[0]->sum^c[1]->sum;}
void node::pushdown()
{
    if(tur) c[0]->reverse(),c[1]->reverse(),tur=0;
}
int isr(node *x){return x!=x->fa->c[0]&&x!=x->fa->c[1];}
void rotate(node *x)
{
    if(isr(x)) return ;
    node *y=x->fa; int l=(x==y->c[1]),r=l^1;
    y->c[l]=x->c[r]; x->c[r]->fa=y;
    x->c[r]=y; x->fa=y->fa;
    if(!isr(y)) y->fa->c[(y==y->fa->c[1])]=x;
    y->fa=x; y->pushup(); x->pushup();
}
void downall(node *x)
{
    if(!isr(x)) downall(x->fa);
    x->pushdown();
}
void splay(node *x)
{
    downall(x);
    while(!isr(x))
    {
        node *y=x->fa;
        if(!isr(y)) rotate((x==y->c[0])^(y==y->fa->c[0])?x:y);
        rotate(x);
    }
}
void access(node *x)
{
    node *tmp=null;
    while(x!=null)
    {
        splay(x);
        x->c[1]=tmp; x->pushup();
        tmp=x; x=x->fa;
    }
}
void moveroot(node *x)
{
    access(x); splay(x); x->reverse();
}
int ats(node *x,node *y)
{
    while(x->fa!=null) x=x->fa;
    while(y->fa!=null) y=y->fa;
    return x==y;
}
void link(node *x,node *y)
{
    moveroot(x); x->fa=y;
}
void cut(node *x,node *y)
{
    moveroot(x); access(y); splay(y);
    if(y->c[0]==x&&x->c[1]==null) x->fa=y->c[0]=null,y->pushup();
}
int main()
{
    int n,m,i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&x);
        t[i]=new node(x);
    }
    while(m--)
    {
        scanf("%d",&i);
        switch(i)
        {
            case 0:
            {
                scanf("%d%d",&x,&y);
                moveroot(t[x]); access(t[y]); splay(t[y]);
                printf("%d\n",t[y]->sum); break;
            }
            case 1:
            {
                scanf("%d%d",&x,&y);
                if(!ats(t[x],t[y])) link(t[x],t[y]);
                break;
            }
            case 2:
            {
                scanf("%d%d",&x,&y);
                cut(t[x],t[y]);
                break;
            }
            case 3:
            {
                scanf("%d%d",&x,&y);
                access(t[x]); splay(t[x]);
                t[x]->w=y; t[x]->pushup(); break;
            }
        }
    }
    return 0;
}