P3690 【模板】Link Cut Tree (动态树)


题面

https://www.luogu.org/problem/P3690

题解

#include<cstdio>
#include<iostream>
using namespace std;

int f[300050],ch[300050][2];
int s[300050],v[300050];
int stk[300050];
bool r[300050];
int n,m;

bool opt(int x) {
  return ch[f[x]][1]==x;
}

bool notroot(int x) {
  return ch[f[x]][0]==x || ch[f[x]][1]==x;
}

void pushup(int x) {
  s[x]=s[ch[x][0]]^s[ch[x][1]]^v[x];
}

void pushr(int x) {
  if (!r[x]) return;
  r[x]=false;
  swap(ch[x][0],ch[x][1]); r[ch[x][0]]^=1; r[ch[x][1]]^=1;
}

void rotate(int x) {
  int y=f[x],z=f[y],s=opt(x);
  if (notroot(y)) ch[z][opt(y)]=x; f[x]=z;
  ch[y][s]=ch[x][1^s]; if (ch[x][1^s]) f[ch[x][1^s]]=y;
  ch[x][1^s]=y; f[y]=x;
  pushup(y); pushup(x);
}

void splay(int x) {
  int y=x,t=0;
  while(notroot(y)) stk[t++]=y,y=f[y];
  stk[t]=y;
  while (t>=0) pushr(stk[t]),t--;
  while (notroot(x)) {
    if (!notroot(f[x])) rotate(x);
    else {
      if (opt(x)==opt(f[x]) && notroot(f[x])) rotate(f[x]),rotate(x);
      else rotate(x),rotate(x);
    }
  }
}

void access(int x) {
  int y=0;
  while (x) {
    splay(x);
    ch[x][1]=y;pushup(x);
    y=x;x=f[x];
  }
}

void makeroot(int x) {
  access(x); splay(x);
  r[x]^=1;
  pushr(x);
}

int findroot(int x) {
  access(x); splay(x);
  while (ch[x][0]) pushr(x),x=ch[x][0];
  return x;
}

void split(int x,int y) {
  makeroot(x);
  access(y); splay(y);
}

void link(int x,int y) {
  makeroot(x);
  if (findroot(y)!=x) f[x]=y;
}

void cut(int x,int y) {
  makeroot(x);
  if (findroot(y)==x && f[x]==y && !ch[x][1]) {
    f[x]=ch[y][0]=0;
    pushup(y);
  }
}

int main(){
  int i,op,x,y;
  scanf("%d %d",&n,&m);
  for (i=1;i<=n;i++) scanf("%d",&v[i]);
  for (i=1;i<=m;i++) {
    scanf("%d %d %d",&op,&x,&y);
    if (op==0) split(x,y),pushup(y),printf("%d\n",s[y]); 
    else if (op==1) link(x,y);
    else if (op==2) cut(x,y);
    else splay(x),v[x]=y;
  }
  return 0;
}

优质内容筛选与推荐>>
1、【模板】冰茶姬(大概是全的?)
2、Ubuntu开放对外端口
3、课后作业3
4、python-docx编辑word表格
5、第3次作业


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号