3282. Tree【LCT】

Description

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。

操作有４种。操作从０到３编号。点从１到Ｎ编号。

０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。

保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

Input

第１行两个整数,分别为Ｎ和Ｍ,代表点数和操作数。

第２行到第Ｎ＋１行,每行一个整数,整数在［１,１０＾９］内,代表每个点的权值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行,每行三个整数,分别代表操作类型和操作所需的量。

１＜＝Ｎ，Ｍ＜＝３０００００

Output

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

Sample Input

3 3
1
2
3
1 1 2
0 1 2
0 1 1

Sample Output

3
1

还是LCT模板题（话说我怎么天天做板子题）

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (300000+100)

 using namespace std;

 int Father[N],Son[N][],Rev[N],Val[N],Xor[N];

 int n,m;

 void Update(int x){Xor[x]=Val[x]^Xor[Son[x][]]^Xor[Son[x][]];}

 int Get(int x) {return Son[Father[x]][]==x;}

 int Is_root(int x) {return Son[Father[x]][]!=x && Son[Father[x]][]!=x;}

 void Rotate(int x)

 {

     int wh=Get(x);

     int fa=Father[x],fafa=Father[fa];

     if (!Is_root(fa)) Son[fafa][Son[fafa][]==fa]=x;

     Father[fa]=x;

     Son[fa][wh]=Son[x][wh^];

     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;

     Father[x]=fafa;

     Son[x][wh^]=fa;

     Update(fa);

     Update(x);

 }

 void Pushdown(int x)

 {

     if (Rev[x] && x)

     {

         if (Son[x][]) Rev[Son[x][]]^=;

         if (Son[x][]) Rev[Son[x][]]^=;

         swap(Son[x][],Son[x][]);

         Rev[x]=;

     }

 }

 int Push(int x)

 {

     if (!Is_root(x)) Push(Father[x]);

     Pushdown(x);

 }

 void Splay(int x)

 {

     Push(x);

     for (int fa; !Is_root(x); Rotate(x))

         if (!Is_root(fa=Father[x]))

             Rotate(Get(fa)==Get(x)?fa:x);

 }

 void Access(int x) {for (int y=;x;y=x,x=Father[x]) Splay(x),Son[x][]=y,Update(x);}

 int Find_root(int x) {Access(x); Splay(x); while (Son[x][]) x=Son[x][]; return x;}

 void Make_root(int x) {Access(x); Splay(x); Rev[x]^=;}

 void Link(int x,int y) {Make_root(x); Father[x]=y;}

 void Cut(int x,int y) {Make_root(x); Access(y); Splay(y); Son[y][]=Father[x]=;}

 void Query(int x,int y){Make_root(x);Access(y);    Splay(y); printf("%d\n",Xor[y]);}

 int main()

 {

     int opt,x,y;

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

     for (int i=; i<=n; ++i)

         scanf("%d",&Val[i]),Xor[i]=Val[i];

     for (int i=; i<=m; ++i)

     {

         scanf("%d%d%d",&opt,&x,&y);

         if (opt==) Query(x,y);

         if (opt== && Find_root(x)!=Find_root(y)) Link(x,y);

         if (opt== && Find_root(x)==Find_root(y)) Cut(x,y);

         if (opt==) Access(x),Splay(x),Val[x]=y,Update(x);

     }

 }

秒客网