BZOJ 3282 Tree Link-Cut-Tree(LCT)

时间:2024-07-05 09:34:02

题目大意:

给定N个点以及每一个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。

0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。

2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。

3:后接两个整数(x,y),代表将点X上的权值变成Y。

仅仅有会员才知道的世界。。。有个会员的大神真好

LCT的入门题,切完2631之后这个就简单多了。。。Link和Cut的时候注意特判一下连通性就可以

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 300300
using namespace std;
struct abcd{
abcd *fa,*ls,*rs;
int num,xor_sum;
bool rev_mark;
abcd(int x);
void Reverse();
void Push_Up();
void Push_Down();
}*null=new abcd(0),*tree[M];
abcd :: abcd(int x)
{
fa=ls=rs=null;
num=x;xor_sum=x;
rev_mark=0;
}
void abcd :: Reverse()
{
swap(ls,rs);
rev_mark^=1;
}
void abcd :: Push_Up()
{
xor_sum=ls->xor_sum^rs->xor_sum^num;
}
void abcd :: Push_Down()
{
if(fa->ls==this||fa->rs==this)
fa->Push_Down();
if(rev_mark)
{
ls->Reverse();
rs->Reverse();
rev_mark=0;
}
}
void Zig(abcd *x)
{
abcd *y=x->fa;
y->ls=x->rs;
x->rs->fa=y;
x->rs=y;
x->fa=y->fa;
if(y==y->fa->ls)
y->fa->ls=x;
else if(y==y->fa->rs)
y->fa->rs=x;
y->fa=x;
y->Push_Up();
}
void Zag(abcd *x)
{
abcd *y=x->fa;
y->rs=x->ls;
x->ls->fa=y;
x->ls=y;
x->fa=y->fa;
if(y==y->fa->ls)
y->fa->ls=x;
else if(y==y->fa->rs)
y->fa->rs=x;
y->fa=x;
y->Push_Up();
}
void Splay(abcd *x)
{
x->Push_Down();
while(x->fa->ls==x||x->fa->rs==x)
{
abcd *y=x->fa,*z=y->fa;
if(x==y->ls)
{
if(y==z->ls)
Zig(y);
Zig(x);
}
else
{
if(y==z->rs)
Zag(y);
Zag(x);
}
}
x->Push_Up();
}
void Access(abcd *x)
{
abcd *y=null;
while(x!=null)
{
Splay(x);
x->rs=y;
x->Push_Up();
y=x;
x=x->fa;
}
}
void Move_To_Root(abcd *x)
{
Access(x);
Splay(x);
x->Reverse();
}
abcd* Find_Root(abcd *x)
{
for(;x->fa!=null;x=x->fa);
return x;
}
void Link(abcd *x,abcd *y)
{
if( Find_Root(x)==Find_Root(y) )
return ;
Move_To_Root(x);
x->fa=y;
}
void Cut(abcd *x,abcd *y)
{
if( x==y || Find_Root(x)!=Find_Root(y) )
return ;
Move_To_Root(x);
Access(y);
Splay(y);
if(y->ls==x)
{
x->fa=null;
y->ls=null;
y->Push_Up();
}
}
void Change(abcd *x,int y)
{
Splay(x);
x->num=y;
x->Push_Up();
}
int Query(abcd *x,abcd *y)
{
Move_To_Root(x);
Access(y);
Splay(y);
return y->xor_sum;
}
int n,m;
int main()
{
int i,x,y,p;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%d",&x),tree[i]=new abcd(x);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&x,&y);
switch(p)
{
case 0:printf("%d\n", Query(tree[x],tree[y]) );break;
case 1:Link(tree[x],tree[y]);break;
case 2:Cut(tree[x],tree[y]);break;
case 3:Change(tree[x],y); break;
}
}
return 0;
}