[关闭]
@Venous 2018-05-15T21:44:19.000000Z 字数 3730 阅读 993

Link-Cut Tree

知识体系
知识版权所有,未经允许请勿转载哦!


首先明白这个神奇的动态树支持的操作(貌似这个顺序不对)
常见问题形势——

 维护两点的连通 
 维护两点路径权值的和,最大值,最小值,自定义运算值……
 维护LCA,直径,重心,自定义点与点的关系……

烦人的动态操作——

连接两个点(先前是不连通的)
把某个点变成某个点的父亲(先前是不连通的)
断开两个点的连接(先前是联通的)
修改点权,边权等等……

它已为关键字(这是很致命的操作)
首先是用维护原树上链的信息,在同一条链上的用连接,不同的虚边连接这是一个很蛋疼的性质,因而会出现如下一些情况

x是y的父亲,也就是fa[y]=x,但是x并没有y这个儿子,也就是并没有tr[x].ch[0]=y或是tr[x].ch[1]=y
在Splay时可能会将虚边修改为实边

然后还有虚边是怎么连的呢?

称有两棵Splay树A,B,其中B树的根节点是x,x在原树中的父亲是y且y处于A树中,那么则将x向y连一条虚边,我们称为“将辅助树中的根节点连一条虚边指向它在原树中得父亲”

给大家举一个栗子(已"1"为根)

1-2,2-4,2-5,3-6,3-7

那么在LCT中它们则是这么连的(手玩一下大概就懂了)

2-4,2-1,6-3(实边)
2-5,1-6,3-7(虚边)

然后考虑具体模板和操作

首先是Splay中也有的

模板一:Rotate,旋转

这是你中写的

  1. void Rotate(int x)
  2. {
  3. int y=tr[x].fa;
  4. int z=tr[y].fa;
  5. int k=tr[y].ch[1]==x;
  6. tr[z].ch[tr[z].ch[1]==y]=x; tr[x].fa=z;
  7. tr[y].ch[k]=tr[x].ch[k^1]; tr[tr[x].ch[k^1]].fa=y;
  8. tr[x].ch[k^1]=y; tr[y].fa=x;
  9. }

这是你中写的

  1. void Rotate(int x)
  2. {
  3. int y=tr[x].fa;
  4. int z=tr[y].fa;
  5. int k=tr[y].ch[1]==x;
  6. if(!Isroot(y))tr[z].ch[tr[z].ch[1]==y]=x; tr[x].fa=z;
  7. tr[y].ch[k]=tr[x].ch[k^1]; tr[tr[x].ch[k^1]].fa=y;
  8. tr[x].ch[k^1]=y; tr[y].fa=x;
  9. }

所以,用事实说话,其实唯一差距就是加入一句if(!Isroot(y))的判断,也就是如果y是所处中根的话,就不能将z的儿子修改为x,为什么呢?

在之前介绍优(dan)良(teng)性质的时候就介绍了z并不一定有y这个儿子

模板二:Splay

这是你中写的

  1. while(tr[x].fa!=goal)
  2. {
  3. int y=tr[x].fa,z=tr[y].fa;
  4. if(z!=goal)
  5. (tr[z].ch[0]==y)^(tr[y].ch[0]==x)?Rotate(x):Rotate(y);
  6. Rotate(x);
  7. }
  8. if(!goal)root=x;

这是你中写的

  1. //Part 1
  2. zhan[++top]=x;
  3. for(int p=x;!Isroot(p);p=tr[p].fa)
  4. zhan[++top]=tr[p].fa;
  5. while(top)Pushdown(zhan[top--]);
  6. //Part 2
  7. while(!Isroot(x))
  8. {
  9. int y=tr[x].fa,z=tr[y].fa;
  10. if(!Isroot(y))
  11. (tr[y].ch[0]==x)^(tr[z].ch[0]==y)?Rotate(x):Rotate(y);
  12. Rotate(x);
  13. }

咱们首先看Part 2,中说的是z!=goal也就是z不是根的父亲,中是!Isroot(y)也就是y并不是根,所以本质上一样的
然后Part 1存在的意义是用来翻转标记,由于标记需要从上往下,这在之后的会提到

特殊模板

模板三:

  1. return tr[tr[x].fa].ch[0]!=x&&tr[tr[x].fa].ch[1]!=x;

如果x的父亲的两个儿子都不是x的话,就说明x的父亲并没有这个儿子,也就说明x是所处Splay中的根(优良性质)

模板四:

  1. for(int y=0;x;y=x,x=tr[x].fa)
  2. {
  3. Splay(x);
  4. tr[x].ch[1]=y;
  5. Pushup(x);
  6. }

这一部分是把x到原树上的跟节点的路径抠到同一棵中,其余原本的点则断掉,然后具体原理是怎么抠的呢?

具体先把当前的x旋转到该棵Splay中,然后把x的右儿子置为x的假儿子(就是由于优良性质导致的x是y的父亲,但是x并没有y这个儿子),注意原本的x和y是用虚边连接的!

模板五:

  1. void Makeroot(int x)
  2. {
  3. Access(x);
  4. Splay(x);
  5. Reverse(x);
  6. }

这一部分是把x点放到原树的根节点上去,所以不难想到就是++,由于这一部分是更改了树的根节点,也就是树的结构的,所以一定要记得

模板六:

  1. int Findroot(int x)
  2. {
  3. Access(x);
  4. Splay(x);
  5. while(tr[x].ch[0])x=tr[x].ch[0];
  6. return x;
  7. }

这一部分是找到x所在的联通块中的根(能维护连通性),但是这一部分并没有改变树的结构!所以千万不需要,然后要找到原联通块的根,就只需要一直跳左儿子就可以了。

因为己经保证Splay已经保证以深度为关键字,所以深度最小的那个点,就是联通块的根节点,至于Findroot后的LCT树只是将树形变了一下!原树的结构是没有改变的!

模板七:

  1. void Split(int x,int y)
  2. {
  3. Makeroot(x);
  4. Access(y);
  5. Splay(y);
  6. }

这一部分是将LCT树中的x到y的路径给抠出来。所以不难想到是++(这个自己yy一下就好了)

一些打不好会很致命的模板

  1. void Link(int x,int y)
  2. {
  3. Makeroot(x);
  4. if(Findroot(y)!=x)tr[x].fa=y;
  5. }

这一部分就是动态维护树的结构了,在两点之间连边。自己yy一下,不难想到是+if(Findroot(y)!=x),所以如果条件满足的话,就连边就好了!
但是这也是最容易出错的,因为if(Findroot(x)!=Findroot(y))是不够好的

模板八:Cut

  1. void Cut(int x,int y)
  2. {
  3. Makeroot(x);
  4. if(Findroot(y)!=x||tr[x].ch[1]||tr[x].fa!=y)return;
  5. tr[y].ch[0]=tr[x].fa=0;
  6. Pushup(y);
  7. }

这就不用说了吧,将x与y之间的连边断掉(一定要两点在原树中直接有一条边相连)
具体细节也超多的!

Update:5.15

然后有关一些标记下放的问题

翻转标记(Reverse

  1. void Reverse(int x)
  2. {
  3. swap(tr[x].ch[0],tr[x].ch[1]);
  4. tr[x].rev^=1;
  5. }

下放标记(Pushdown

  1. void Pushdown(int x)
  2. {
  3. if(tr[x].rev)
  4. {
  5. if(tr[x].ch[0])
  6. Reverse(tr[x].ch[0]);
  7. if(tr[x].ch[1])
  8. Reverse(tr[x].ch[1]);
  9. tr[x].rev=0;
  10. }
  11. }

然后放一个---[国家集训队]Tree II
这是我有史一以来打过的最长的下放

  1. void pushdown(int x)
  2. {
  3. if(tr[x].mul!=1)
  4. {
  5. ll t=tr[x].mul;
  6. tr[x].v=tr[x].v*t%mod;
  7. if(ls)
  8. tr[ls].sum=tr[ls].sum*t%mod,
  9. tr[ls].add=tr[ls].add*t%mod,
  10. tr[ls].mul=tr[ls].mul*t%mod;
  11. if(rs)
  12. tr[rs].sum=tr[rs].sum*t%mod,
  13. tr[rs].add=tr[rs].add*t%mod,
  14. tr[rs].mul=tr[rs].mul*t%mod;
  15. tr[x].mul=1;
  16. }
  17. if(tr[x].add)
  18. {
  19. ll t=tr[x].add;
  20. tr[x].v=(tr[x].v+t)%mod;
  21. if(ls)
  22. tr[ls].sum=(tr[ls].sum+t*tr[ls].sz%mod)%mod,
  23. tr[ls].add=(tr[ls].add+t)%mod;
  24. if(rs)
  25. tr[rs].sum=(tr[rs].sum+t*tr[rs].sz%mod)%mod,
  26. tr[rs].add=(tr[rs].add+t)%mod;
  27. tr[x].add=0;
  28. }
  29. if(tr[x].rev)
  30. {
  31. if(ls)
  32. Reverse(ls);
  33. if(rs)
  34. Reverse(rs);
  35. tr[x].rev=0;
  36. }
  37. }

然后至于能维护子树信息的骚操作,就留个坑以后再补吧!

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注