P3690 【模板】Link Cut Tree （动态树）-白红宇

P3690 【模板】Link Cut Tree （动态树）

阅读量：5173 次

发布时间：2019-06-13

本文共 3117 字，大约阅读时间需要 10 分钟。

题目背景

动态树

题目描述

给定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。

输入输出格式

输入格式：

第1行两个整数，分别为n和m，代表点数和操作数。

第2行到第n+1行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。

第n+2行到第n+m+1行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式：

对于每一个0号操作，你须输出x到y的路径上点权的xor和。

输入输出样例

输入样例#1：

3 3 1231 1 20 1 2 0 1 1

输出样例#1：

说明

数据范围： $\leq N, M \leq 3 \cdot {10}^5 1≤N,M≤3⋅105$

solution:

板子。

CODE:

1 #include
     
       2 #define R register int 3 #define I inline void 4 #define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin)) 5 #define lc c[x][0] 6 #define rc c[x][1] 7 using namespace std; 8 const int SZ=1<<19,N=3e5+9; 9 char buf[SZ],*ie=buf+SZ,*ip=ie-1;10 inline int in(){11     G;while(*ip<'-')G;12     R x=*ip&15;G;13     while(*ip>'-'){x*=10;x+=*ip&15;G;}14     return x;15 }16 int f[N],c[N][2],v[N],s[N],st[N];17 bool r[N];18 inline bool nroot(R x){
     //判断节点是否为一个Splay的根（与普通Splay的区别1）19     return c[f[x]][0]==x||c[f[x]][1]==x;20 }//原理很简单，如果连的是轻边，他的父亲的儿子里没有它21 I pushup(R x){
     //上传信息22     s[x]=s[lc]^s[rc]^v[x];23 }24 I pushr(R x){R t=lc;lc=rc;rc=t;r[x]^=1;}//翻转操作25 I pushdown(R x){
     //判断并释放懒标记26     if(r[x]){27         if(lc)pushr(lc);28         if(rc)pushr(rc);29         r[x]=0;30     }31 }32 I rotate(R x){
     //一次旋转33     R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];34     if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;//额外注意if(nroot(y))语句，此处不判断会引起致命错误（与普通Splay的区别2）35     if(w)f[w]=y;f[y]=x;f[x]=z;36     pushup(y);37 }38 I splay(R x){
     //只传了一个参数，因为所有操作的目标都是该Splay的根（与普通Splay的区别3）39     R y=x,z=0;40     st[++z]=y;//st为栈，暂存当前点到根的整条路径，pushdown时一定要从上往下放标记（与普通Splay的区别4）41     while(nroot(y))st[++z]=y=f[y];42     while(z)pushdown(st[z--]);43     while(nroot(x)){44         y=f[x];z=f[y];45         if(nroot(y))46             rotate((c[y][0]==x)^(c[z][0]==y)?x:y);47         rotate(x);48     }49     pushup(x);50 }51 /*当然了，其实利用函数堆栈也很方便，代替上面的手工栈，就像这样52 I pushall(R x){53     if(nroot(x))pushall(f[x]);54     pushdown(x);55 }*/56 I access(R x){
     //访问57     for(R y=0;x;x=f[y=x])58         splay(x),rc=y,pushup(x);59 }60 I makeroot(R x){
     //换根61     access(x);splay(x);62     pushr(x);63 }64 int findroot(R x){
     //找根（在真实的树中的）65     access(x);splay(x);66     while(lc)pushdown(x),x=lc;67     splay(x);68     return x;69 }70 I split(R x,R y){
     //提取路径71     makeroot(x);72     access(y);splay(y);73 }74 I link(R x,R y){
     //连边75     makeroot(x);76     if(findroot(y)!=x)f[x]=y;77 }78 I cut(R x,R y){
     //断边79     makeroot(x);80     if(findroot(y)==x&&f[y]==x&&!c[y][0]){81         f[y]=c[x][1]=0;82         pushup(x);83     }84 }85 int main()86 {87     R n=in(),m=in();88     for(R i=1;i<=n;++i)v[i]=in();89     while(m--){90         R type=in(),x=in(),y=in();91         switch(type){92         case 0:split(x,y);printf("%d\n",s[y]);break;93         case 1:link(x,y);break;94         case 2:cut(x,y);break;95         case 3:splay(x);v[x]=y;//先把x转上去再改，不然会影响Splay信息的正确性96         }97     }98     return 0;99 }