[关闭]
@xzyxzy 2019-02-21T10:34:35.000000Z 字数 6374 阅读 3822

Link-Cut-Tree

数据结构

作业部落:https://www.zybuluo.com/xzyxzy/note/1027479

评论地址:https://www.cnblogs.com/xzyxzy/p/8410780.html


一、概述

,动态树的一种,又可以又可以
引用:http://www.cnblogs.com/zhoushuyu/p/8137553.html

二、题目

初步

进阶

Qtree系列

考试题


三、支持操作

I 维护联通性

维护两点联通性,较易,例题Cave 洞穴勘测

II 维护树链信息

正是由于这个LCT可以代替树链剖分的关于链的操作(关于子树信息是无法做到的,感谢@cjfdf斧正「2018.2.25」)
运用操作把这条链抠出来操作
例题【模板】Link Cut Tree
这是的最大作用之一,几乎在每道题中都有体现
PS:树剖的常数小且相对容易调试,建议能写树剖则写(如“初步”的后三题,没有删边操作)

III 维护生成树

例题:“初步”中水管局长温暖会指引我们前行

这里较为重要,理解需要时间

引入:一条路径的权值定义为该路径上所有边的边权最大值,问x到y的所有路径中,路径权值最小的路径的权值是多少,要求支持加边或删边,求解
解决
pushup片段
  1. int Getmax(int x,int y){return t[x].val>t[y].val?x:y;}
  2. void pushup(int x){t[x].id=Getmax(x,Getmax(t[lc].id,t[rc].id));}

IV 维护边双联通分量

例题星球联盟长跑

这里难懂,慢慢体会

解释

边双联通,其实就是说有两条不相交的路径可以到达
这里表述也不是特别清楚,这两道题的意思是————把环缩点
两道题一句话题意:求x,y路径上点(超级点)的siz(val)之和

实现

类似于缩点,遇到环,暴力DFS把所有点指向一个标志点
在之后凡要用到一个点就x=f[x]
相当于踏入这个环就改成踏进这个超级点
能够保证总复杂度为(虽然星球联盟暴力不缩点也可以过)

核心代码片段
  1. //并查集find
  2. int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
  3. //读进来的时候就改成超级点
  4. int x=read(),y=read();x=find(x);y=find(y);
  5. //goal为超级点
  6. void DFS(int x,int goal)
  7. {
  8. if(lc)DFS(lc,goal);
  9. if(rc)DFS(rc,goal);
  10. if(x!=goal){f[x]=goal;siz[goal]+=siz[x];}
  11. }
  12. //每次访问点的时候都访问其find
  13. void rotate(int x)
  14. {
  15. int y=find(t[x].fa),z=find(t[y].fa);
  16. ...
  17. }
  18. void Access(int x){for(int y=0;x;y=x,x=find(t[x].fa)){splay(x);t[x].ch[1]=y;pushup(x);}}
  19. ...

V 维护原图信息

例题大融合动态树

难懂,烦请细细品味

解释
实现

的目的是使得x没有实儿子,那么虚儿子便是原子树的信息
因为的实儿子中有可能有点是原图中的儿子,那么只算虚儿子会算不全,都算会多算
以维护为例:
记录每个点的表示虚儿子信息,表示实儿子和虚儿子的信息
需要改动的地方只有

核心代码片段
  1. //要改变的两个操作
  2. void Access(int x)
  3. {
  4. for(int y=0;x;y=x,x=t[x].fa)
  5. {
  6. splay(x);
  7. t[x].Rs=t[x].Rs+t[rc].siz-t[y].siz;//把一个实儿子变成虚儿子要+t[rx].siz,把一个虚儿子变成实儿子要-t[y].siz
  8. rc=y;pushup(x);
  9. }
  10. }
  11. void link(int x,int y){makeroot(x);makeroot(y);t[x].fa=y;t[y].Rs+=t[x].siz;}//link要makeroot(y)因为连上x后y到该棵splay的根都有影响

注意的是这里调用的都是也就是这棵子树所有的值,而不是这个点的值!!
由于这个原因共价大爷游长沙调试了半个小时


四、做题经验

1、辨别

如何看出一道题要用————动态加/删边!

2、常数

只有加边操作时,维护两点是否联通请用并查集
在以下题目会TLE:温暖会指引我们前行长跑

3、易错

一旦访问就要pushdown!!

4、所谓奇技淫巧


这是[LNOI2014]LCA的题面,方法是在这个区间内每个点到根的路径+1,统计z到根的路径之和即为答案,处理区间时,很多时候用
比如说还有这道题:2018.1.25区间子图(考试题)

代码

Luogu LCT模板

  1. //注释详尽版本
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<set>
  7. using namespace std;
  8. int read()
  9. {
  10. char ch=getchar();
  11. int h=0;
  12. while(ch>'9'||ch<'0')ch=getchar();
  13. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  14. return h;
  15. }
  16. const int MAXN=300001;
  17. set<int>Link[MAXN];
  18. int N,M,val[MAXN],zhan[MAXN],top=0;
  19. struct Splay{int val,sum,rev,ch[2],fa;}t[MAXN];
  20. void Print()
  21. {
  22. for(int i=1;i<=N;i++)
  23. printf("%d:val=%d,fa=%d,lc=%d,rc=%d,sum=%d,rev=%d\n",i,t[i].val,t[i].fa,t[i].ch[0],t[i].ch[1],t[i].sum,t[i].rev);
  24. }
  25. void pushup(int x)//向上维护异或和
  26. {
  27. t[x].sum=t[t[x].ch[0]].sum^t[t[x].ch[1]].sum^t[x].val;//异或和
  28. }
  29. void reverse(int x)//打标记
  30. {
  31. swap(t[x].ch[0],t[x].ch[1]);
  32. t[x].rev^=1;//标记表示已经翻转了该点的左右儿子
  33. }
  34. void pushdown(int x)//向下传递翻转标记
  35. {
  36. if(!t[x].rev)return;
  37. if(t[x].ch[0])reverse(t[x].ch[0]);
  38. if(t[x].ch[1])reverse(t[x].ch[1]);
  39. t[x].rev=0;
  40. }
  41. bool isroot(int x)//如果x是所在链的根返回1
  42. {
  43. return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;
  44. }
  45. void rotate(int x)//Splay向上操作
  46. {
  47. int y=t[x].fa,z=t[y].fa;
  48. int k=t[y].ch[1]==x;
  49. if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;//Attention if()
  50. t[x].fa=z;//注意了
  51. /*
  52. 敲黑板:这个时候y为Splay的根,把x绕上去后
  53. x的父亲是z!表示这个splay所表示的原图中的链的链顶的父亲
  54. 这正是splay根的父亲表示的是链顶的父亲的集中体现!
  55. */
  56. t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].fa=y;
  57. t[x].ch[k^1]=y;t[y].fa=x;
  58. pushup(y);
  59. }
  60. void splay(int x)//把x弄到根
  61. {
  62. zhan[++top]=x;
  63. for(int pos=x;!isroot(pos);pos=t[pos].fa)zhan[++top]=t[pos].fa;
  64. while(top)pushdown(zhan[top--]);
  65. while(!isroot(x))
  66. {
  67. int y=t[x].fa,z=t[y].fa;
  68. if(!isroot(y))
  69. /*
  70. 这个地方和普通Splay有所不同:
  71. 普通的是z!=goal,z不是根的爸爸
  72. 这个是y!=root,y不是根
  73. 所以实质是一样的。。。
  74. */
  75. (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
  76. rotate(x);
  77. }
  78. pushup(x);
  79. }
  80. void Access(int x)
  81. {
  82. for(int y=0;x;y=x,x=t[x].fa){splay(x);t[x].ch[1]=y;pushup(x);}
  83. /*
  84. Explaination:
  85. 函数功能:把x到原图的同一个联通块的root弄成一条链,放在同一个Splay中
  86. 首先令x原先所在splay的最左端(x所在链的链顶)为u
  87. 那么x-u一定保留在x-root的路径中,那么直接断掉x的右儿子
  88. 然后y是上一个这么处理的链的Splay所在的根
  89. 在之前,y向x连了一条虚边(y的fa是x,x的ch不是y)
  90. 那么只要化虚为实就可以了
  91. */
  92. }
  93. void makeroot(int x)//函数功能:把x拎成原图的根
  94. {
  95. Access(x);splay(x);//把x和根先弄到一起
  96. reverse(x);//然后打区间翻转标记,应该在根的地方打但是找不到根所以要splay(x)
  97. /*
  98. 这里很神奇的一个区间翻转标记,那么从上往下是root-x,翻转完区间就是x-root
  99. 这样子相当于(这里打一个神奇的比喻)
  100. 一根棒子上面有一些平铺的长毛,原先是向上拉,区间翻转后就向下拉
  101. | ↑ |
  102. ----|---- /|\ \ \|/ /
  103. ----|---- / | \ \ | /
  104. ----|---- / /|\ \ \ \|/ /
  105. ----|---- / | \ \ | /
  106. ----|---- / /|\ \ \ \|/ /
  107. ----|---- / | \ \ | /
  108. ----|---- / /|\ \ \|/
  109. | | ↓
  110. 哈哈哈夸我~
  111. */
  112. }
  113. int Findroot(int x)//函数功能:找到x所在联通块的splay的根
  114. {
  115. Access(x);splay(x);
  116. while(t[x].ch[0])x=t[x].ch[0];
  117. return x;
  118. }
  119. void split(int x,int y)//函数功能:把x到y的路径抠出来
  120. {
  121. makeroot(x);//先把x弄成原图的根
  122. Access(y);//再把y和根的路径弄成重链
  123. splay(y);//那么就是y及其左子树存储的信息了
  124. /*
  125. 关于这里为什么要splay(y):
  126. 可以发现,makeroot后x为splay的根
  127. 但是Access之后改变了根(这就是为什么凡是Access都后面跟了splay)
  128. 所以要找到根最方便就是splay,至于splayx还是y,都可以
  129. */
  130. }
  131. void link(int x,int y)//函数功能:连接x,y所在的两个联通块
  132. {
  133. makeroot(x);//把x弄成其联通块的根
  134. t[x].fa=y;//连到y上(虚边)
  135. Link[x].insert(y);Link[y].insert(x);
  136. }
  137. void cut(int x,int y)//函数功能:割断x,y所在的两个联通块
  138. {
  139. split(x,y);
  140. t[y].ch[0]=t[x].fa=0;
  141. Link[x].erase(y);Link[y].erase(x);
  142. /*
  143. 这里会出现一个这样的情况:
  144. 图中x和y并未直接连边,但是splay中有可能直接相连
  145. 所以一定要用set(map会慢)维护实际的连边
  146. 不然会出现莫名错误(大部分数据可以水过去,但是subtask...)
  147. */
  148. }
  149. int main()
  150. {
  151. N=read();M=read();
  152. for(int i=1;i<=N;i++)
  153. t[i].sum=t[i].val=read();//原图中结点编号就是Splay结点编号
  154. for(int i=1;i<=M;i++)
  155. {
  156. int op=read(),x=read(),y=read();
  157. if(op==0)//x到y路径异或和
  158. {
  159. split(x,y);//抠出路径
  160. printf("%d\n",t[y].sum);
  161. }
  162. if(op==1)//连接x,y
  163. {
  164. if(Findroot(x)^Findroot(y))
  165. link(x,y);//x,y不在同一联通块里
  166. }
  167. if(op==2)//割断x,y
  168. {
  169. if(Link[x].find(y)!=Link[x].end())
  170. cut(x,y);//x,y在同一联通块
  171. }
  172. if(op==3)//把x点的权值改成y
  173. {
  174. Access(x);//把x到根的路径设置为重链
  175. splay(x);//把x弄到该链的根结点
  176. t[x].val=y;
  177. pushup(x);//直接改x的val并更新
  178. }
  179. //printf("i=%d\n",i);
  180. //Print();
  181. }
  182. return 0;
  183. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注