[关闭]
@zzzc18 2017-06-21T14:59:06.000000Z 字数 2371 阅读 1447

Link-Cut-Tree

LCT


讲解1
讲解2

题目:洛谷模板题

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define MAXN 300005
  4. using namespace std;
  5. int n,m;
  6. class Link_Cut_Tree{
  7. public:
  8. struct T_T{
  9. int lazy,ls,rs,fa,val;
  10. };
  11. bool isroot(int x){
  12. return !(tree[tree[x].fa].ls==x||tree[tree[x].fa].rs==x);
  13. }
  14. void pushdown(int x){
  15. if(tree[x].lazy){
  16. tree[x].lazy=0;
  17. tree[tree[x].ls].lazy^=1;
  18. tree[tree[x].rs].lazy^=1;
  19. swap(tree[x].ls,tree[x].rs);
  20. }
  21. }
  22. void clean(){
  23. tree[0].ls=tree[0].rs=tree[0].val=tree[0].lazy=0;
  24. }
  25. void rotate(int x){
  26. int y=tree[x].fa,z=tree[y].fa;
  27. if(tree[tree[y].fa].ls==y || tree[tree[y].fa].rs==y){
  28. if(tree[z].ls==y)
  29. tree[z].ls=x;
  30. else
  31. tree[z].rs=x;
  32. }
  33. tree[x].fa=z;
  34. tree[y].fa=x;
  35. if(tree[y].ls==x){
  36. tree[tree[x].rs].fa=y;
  37. tree[y].ls=tree[x].rs;
  38. tree[x].rs=y;
  39. }
  40. else{
  41. tree[tree[x].ls].fa=y;
  42. tree[y].rs=tree[x].ls;
  43. tree[x].ls=y;
  44. }
  45. up(y);up(x);
  46. clean();
  47. }
  48. int que[MAXN];
  49. void splay(int x){
  50. int y,z;int top=1;
  51. que[top]=x;
  52. for(int i=x;!isroot(i);i=tree[i].fa)
  53. que[++top]=tree[i].fa;
  54. for(int i=top;i;i--)
  55. pushdown(que[i]);
  56. while(tree[tree[x].fa].ls==x||tree[tree[x].fa].rs==x){
  57. y=tree[x].fa;z=tree[y].fa;
  58. if(tree[tree[y].fa].ls==y||tree[tree[y].fa].rs==y){
  59. if((tree[y].ls==x && tree[z].rs==y)||(tree[y].rs==x && tree[z].ls==y))
  60. rotate(x);
  61. else
  62. rotate(y);
  63. }
  64. rotate(x);
  65. }
  66. }
  67. T_T tree[MAXN];
  68. //////////////////////////////////////////////////////////////////////////////////////////
  69. int xr[MAXN];
  70. void up(int x){
  71. xr[x]=xr[tree[x].ls]^xr[tree[x].rs]^tree[x].val;
  72. }
  73. void access(int x){
  74. int t=0;
  75. while(x){
  76. splay(x);
  77. tree[x].rs=t;
  78. up(x);
  79. t=x;
  80. x=tree[x].fa;
  81. }
  82. }
  83. void makeroot(int x){
  84. access(x);
  85. splay(x);
  86. tree[x].lazy^=1;
  87. }
  88. int F(int x){
  89. access(x);
  90. splay(x);
  91. while(tree[x].ls)
  92. x=tree[x].ls;
  93. return x;
  94. }
  95. void spilt(int x,int y){
  96. makeroot(x);
  97. access(y);
  98. splay(y);
  99. }
  100. void cut(int x,int y){
  101. spilt(x,y);
  102. if(tree[y].ls==x){
  103. tree[y].ls=0;
  104. tree[x].fa=0;
  105. }
  106. }
  107. void link(int x,int y){
  108. makeroot(x);
  109. tree[x].fa=y;
  110. }
  111. void DEBUG(){
  112. int k;
  113. for(k=1;k<=n;k++){
  114. printf("No. %2d:val=%d|ls=%d|rs=%d|fa=%d|\n",k,tree[k].val,tree[k].ls,tree[k].rs,tree[k].fa);
  115. }
  116. }
  117. }LCT;
  118. int main(){
  119. freopen("LCT.in","r",stdin);
  120. freopen("my.out","w",stdout);
  121. scanf("%d%d",&n,&m);
  122. int i;
  123. for(i=1;i<=n;i++){
  124. scanf("%d",&LCT.xr[i]);
  125. LCT.tree[i].val=LCT.xr[i];
  126. }
  127. for(i=1;i<=m;i++){
  128. int opt,x,y;
  129. scanf("%d",&opt);
  130. scanf("%d%d",&x,&y);
  131. if(opt==0){
  132. LCT.spilt(x,y);
  133. printf("%d\n",LCT.xr[y]);
  134. }
  135. if(opt==1){
  136. int xx=LCT.F(x),yy=LCT.F(y);
  137. //printf("%d %d\n",xx,yy);
  138. if(xx!=yy)
  139. LCT.link(x,y);
  140. }
  141. if(opt==2){
  142. int xx=LCT.F(x),yy=LCT.F(y);
  143. if(xx==yy)
  144. LCT.cut(x,y);
  145. }
  146. if(opt==3){
  147. LCT.access(x);
  148. LCT.splay(x);
  149. LCT.tree[x].val=y;
  150. LCT.up(x);
  151. }
  152. //if(i%500==0)
  153. //LCT.DEBUG();
  154. }
  155. return 0;
  156. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注