首页 > 代码库 > BZOJ3282: Tree

BZOJ3282: Tree

2024-08-06 15:18:28   216人阅读

3282: Tree

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 528  Solved: 200
[Submit][Status]

Description

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。

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

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

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

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

 

 

 

Input

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

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

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

 

 

 

 

 

 

 

Output

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

Sample Input

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

Sample Output

3
1

HINT

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

Source

动态树

题解：

裸LCT。

成为第200个AC此题的人并且status进了第一版并且代码长度最短233

代码：

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 500000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26     int x=0,f=1;char ch=getchar(); 27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29     return x*f; 30 } 31 int n,m,v[maxn],sum[maxn],c[maxn][2],fa[maxn],sta[maxn],top; 32 bool rev[maxn]; 33 inline bool isroot(int x) 34 { 35     return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; 36 } 37 inline void pushup(int x) 38 { 39     sum[x]=v[x]^sum[c[x][0]]^sum[c[x][1]]; 40 } 41 inline void rever(int x) 42 { 43     rev[x]^=1; 44     swap(c[x][0],c[x][1]); 45 } 46 inline void pushdown(int x) 47 { 48     if(!rev[x])return; 49     rever(c[x][0]);rever(c[x][1]); 50     rev[x]=0; 51 } 52 inline void rotate(int x) 53 { 54     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 55     if(!isroot(y))c[z][c[z][1]==y]=x; 56     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 57     c[y][l]=c[x][r];c[x][r]=y; 58     pushup(y);pushup(x); 59 } 60 inline void splay(int x) 61 { 62     int top=0;sta[++top]=x; 63     for(int y=x;!isroot(y);y=fa[y])sta[++top]=fa[y]; 64     for(;top;)pushdown(sta[top--]); 65     while(!isroot(x)) 66     { 67         int y=fa[x],z=fa[y]; 68         if(!isroot(y)) 69         { 70             if(c[z][0]==y^c[y][0]==x)rotate(x);else rotate(y); 71         } 72         rotate(x); 73     } 74 } 75 inline void access(int x) 76 { 77     for(int y=0;x;x=fa[x]) 78     { 79         splay(x);c[x][1]=y;pushup(x);y=x; 80     } 81 } 82 inline void makeroot(int x) 83 { 84     access(x);splay(x);rever(x); 85 } 86 inline void split(int x,int y) 87 { 88     makeroot(x);access(y);splay(y); 89 } 90 inline int findroot(int x) 91 { 92     access(x); 93     while(!isroot(x))x=fa[x]; 94     return x; 95 } 96 inline void link(int x,int y) 97 { 98     if(findroot(x)==findroot(y))return; 99     makeroot(x);fa[x]=y;splay(x);100 }101 inline void cut(int x,int y)102 {103     split(x,y);if(c[y][0]==x)c[y][0]=fa[x]=0;104 }105 int main()106 {107     freopen("input.txt","r",stdin);108     freopen("output.txt","w",stdout);109     n=read();m=read();110     for1(i,n)v[i]=sum[i]=read();111     while(m--)112     {113         int ch=read(),x=read(),y=read();114         if(ch==1)link(x,y);115         else if(ch==2)cut(x,y);116         else if(ch==3)makeroot(x),v[x]=y,pushup(x);117         else if(x==y)printf("%d\n",v[x]);118         else split(x,y),printf("%d\n",sum[y]);119     }120     return 0;121 }
View Code

 

BZOJ3282: Tree


联系
我们