clu pda col make class getchar() root 动态树 pan
https://www.luogu.org/problemnew/show/3690这大概还是一道模板题目
- #include<cstdio>
- #include<algorithm>
- const int maxn = 320007;
- inline int read() {
- int x=0,f=1;char c=getchar();
- while(c<'0'||c>'9') {
- if(c=='-')f=-1;c=getchar();
- }
- while(c<='9'&&c>='0') {
- x=x*10+c-'0',c=getchar();
- }
- return x*f;
- }
- #define lc ch[x][0]
- #define rc ch[x][1]
- bool rev[maxn];
- int stack[maxn],top;
- int ans[maxn],v[maxn];
- int fa[maxn],ch[maxn][2];
- bool isroot(int x) {
- return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;
- }
- void update(int x){
- ans[x]=ans[lc]^ans[rc]^v[x];
- }
- void pushdown(int x) {
- if(rev[x]) {
- rev[x]=0;rev[lc]^=1;rev[rc]^=1;
- std::swap(lc,rc);
- }
- return;
- }
- void rotate(int x) {
- int y=fa[x],z=fa[y],d=(ch[y][1]==x)^1;
- if(!isroot(y)) ch[z][ch[z][1]==y]=x;
- fa[x]=z;
- ch[y][d^1]=ch[x][d],fa[ch[x][d]]=y;
- ch[x][d]=y;fa[y]=x;
- return update(y),update(x);
- }
- void splay(int x) {
- stack[++top]=x;
- for(int i=x;!isroot(i);i=fa[i])
- stack[++top]=fa[i];
- while(top)pushdown(stack[top--]);
- while(!isroot(x)) {
- int y=fa[x],z=fa[y];
- if(!isroot(y)) {
- if(ch[y][1]==x^ch[z][1]==y)rotate(x);
- else rotate(y);
- }
- rotate(x);
- }
- return ;
- }
- void access(int x) {
- for(int i=0;x;i=x,x=fa[x]) {
- splay(x),ch[x][1]=i,update(x);
- }
- return ;
- }
- void makeroot(int x) {
- access(x);splay(x);rev[x]^=1;
- return;
- }
- void split(int x,int y) {
- makeroot(x),access(y);return splay(y);
- }
- void cut(int x,int y) {
- split(x,y);
- ch[y][0]=fa[ch[y][0]]=0;
- return;
- }
- void link(int x,int y) {
- makeroot(x),fa[x]=y;return splay(x);
- }
- int find(int x) {
- for(access(x),splay(x);ch[x][0];x=ch[x][0]);
- return x;
- }
- int query(int x,int y) {
- split(x,y);
- return ans[y];
- }
- void modify(int x,int w) {
- access(x),splay(x),v[x]=w;
- return update(x);
- }
- int main() {
- int n,m;
- n=read(),m=read();
- for(int i=1;i<=n;++i) {
- v[i]=read();ans[i]=v[i];
- }
- for(int op,x,y,i=1;i<=m;++i) {
- op=read(),x=read(),y=read();
- if(!op)
- printf("%d\n",query(x,y));
- else if(op==1) {
- if(find(x)!=find(y)) link(x,y);
- }
- else if(op==2) {
- if(find(x)==find(y))cut(x,y);
- }
- else modify(x,y);
- }
- return 0;
- }
luogu P3690 【模板】Link Cut Tree (动态树)
clu pda col make class getchar() root 动态树 pan
原文:https://www.cnblogs.com/sssy/p/8150952.html
来源: http://www.bubuko.com/infodetail-2445623.html