[动态树]Link-Cut Tree

[原帖地址](http://www.aiuxian.com/article/p-2284697.html) 自己简单研究了下动态树，就先来一发博客吧 动态树 其实很多人都把LCT和动态树搞混了，所以我们先阐明一下定义。 动态树问题 ——就是会动的树上的问题(⊙v⊙) 会动——就是树的形态或权值是会变化的 常见问题形势—— 维护两点的连通性 维护两点路径权值的和，最大值，最小值，自定义运算值…… 维护LCA，直径，重心，自定义点与点的关系…… 烦人的动态操作—— 连接两个点(先前是不连通的) 把某个点变成某个点的父亲(先前是不连通的) 断开两个点的连接(先前是联通的) 修改点权，边权等等…… 嗯，这种题一看就是裸数据结构对吧 所以就有了Tarjan发明的link-cut tree(OrzTarjen爷) link-cut tree基础实现 什么是link-cut tree呢？ 这个东西早在杨哲的集训队作业中提出了：QTREE解法的一些研究 上面的文段有很多正确且严谨的证明，下面不会再给出(OrzOrz) 如果通过上面的文段你已经理解了的话，就可以直接开始做题了！(Orz) 如果我没看懂呢？ 没关系，你只需要两个知识：树链剖分、splay 首先我们需要了解什么是树链剖分 不会的话先看看吧， 有益身心健康 ：树链剖分讲解版 (ps:这个博主很爷但是很奇怪，大家要小心) splay的文章我就不引用了，大家随便百度看书都有 说白了，LCT就是用splay实现动态树的链剖分 我们会发现，树链剖分是用的线段树(至少上面那个是) 可是动态树就是因为会动而讨厌 嗯，如果我们把用线段树维护的东西改成用伸展树，以深度为顺序构建splay 听起来可行的样子 多么和谐！ 可是具体怎么实现呢？ 膜拜一下树链剖分，我们学着用splay维护每次访问的点到它所在树根的链 我们定义 u 的儿子中访问时间最后的点为 w ，若 u 的中以儿子 v 为根的子树包含了 w ，则称 v 为 u 的preferred child(就好像重儿子一样)，自然，我们可以脑补出以下概念: preferred road(u与v的连边)。 preferred path(连续的preferred road所表示的一条路径) 剩下的非preferred child的儿子吗，我们就像轻儿子一样，直接记个path father就好 这里注意一下，path father只能表示两颗splay之间的关系，不能表示两点的关系(通过下面的图你可以明白) 嗯，想像一下，一棵树原本被分成多个线段树，这些线段树又像树一样相连。 唰！线段树变成了splay! 听起来挺不错的样子是吧( ⊙ o ⊙ ) 接下来怎么办？ 别急，我们简单梳理一下 没错，我们把一颗树用splay剖分了 每颗splay对应着一条路径(preferred path) ( ps: 我记得杨哲的paper里说的好像是个 a 什么什么 tree 来着，我这里就直接用preferred path代替了) splay之间构成了一片森林 这样的话原本要维护的森林就可以直接还原 问题来了 怎么取出某个点到所在树根的路径呢(⊙o⊙)？ 我们要把 x 到根的路径变成一条preferred path！ 这就用到了 access 操作 ps: 请大家在下面务必分清原树和路径(preferred path) 嗯哼！ 我们来看看 access 的操作吧 ```cpp void access(int x) { splay(x);//把x splay到所在preferred path的根 cutright(x);//切断x与其右子树的连边 while (splay[x].pf)//若x还存在path father { int u=splay[x].pf; splayup(u);//把u splay到所在preferred path的根 cutright(u);//切断u与其右子树的连边 splay[u].r=x; splay[x].pf=0; splay[x].f=u;//将u的右儿子置为x update(u);//更新u x=u; } return ; } ``` (一头雾水(⊙o⊙)…） 这是干嘛呢？ 这就是把 x 到所在树的树根变成preferred path 其实实现挺直接的，就是利用了splay的伸展性，无脑向上，splay不行就走path father，在路程中顺便更新下preferred path 实现就这几行 这里注意一下： cutright操作只是在preferred path中断开，并不是在原树中断开(也就是说断开后，你要把右儿子的path father置为x) 嗯我是盗图狗 ，右边那个A和G之间好像少了点啥…… 不明觉厉 通过splay的伸展性，切断再重连得到新的preferred path(Tarjan我真的好崇拜您Orz) 这就是 access 诶，说这些有啥用？ 其他的怎么维护呢(⊙v⊙)？ 有了 access ，我们可以做如下操作 1.断开 x 与其父亲的连边。 代码如下 ```cpp void cut(int x) { access(x); splay(x);//取出x到根的路径并将x变成路径根 int l=splay[x].l; splay[x].l=0;//删除x的左孩子 if (l)//如果左孩子存在，即x不为树根 { splay[l].f=0;//断开左孩子和x的连边 splay[l].pf=0;//包括path father也要清零(虽说其本来就是0) update(x); splay(l);//由于l变成了一棵树的根，所以splay它 } return ; } ``` 相信通过代码和解释应该都能搞清楚怎么弄的了(^o^)/~ 我们的splay是以深度为关键字的 如果是 x 和 y 的连边呢？ 你可以稍微维护一下每个节点的父亲 通过 access(x) 和 access(y) 来区分我也不拦着你 2.判断 x 与 y 是否在同一棵树中 我们只需判断 x 和 y 所在的根就可以了 access(x) 之后直接找最左(深度最小)的点就是啦O(∩.∩)O~！ 代码如下 ```cpp int root(int x) { access(x); splay(x);//取出x到根的路径并将x变成路径根 while (splay[x].l) x=splay[x].l;//无脑找最左 splay(x);//因为找出来的是树根，所以splay一发 return x; } ``` 这里我还是给出找爸爸的代码： ```cpp int father(int x) { access(x); splay(x);//取出x到根的路径并将x变成路径根 x=splay[x].l; while (splay[x].r) x=splay[x].r;//无脑找最右 return x; } ``` 3.将 x 变成所在树的树根 代码很简单 ```cpp void beroot(int x) { access(x); splay(x);//说多了不想说了，以后的都直接省略 splay[x].rev^=1;//给x所在路径打上翻转标记 return ; } ``` 诶诶诶(O\_O)？ 这个翻转标记匪夷所思啊！ 仔细一想，我们不过是将整条路径翻转了一下 路径是从 x 到根 翻转一下不就变成根到 x 了？ 多么机智是不是^\_^？ 4.在 x 与 y 中连接一条边(这里是把 y 变成 x 的子树) 嗯，首先 root(x) 不等于 root(y) 接着我们将 y 变成所在子树的根 把 y 的path father置为 x 代码： ```cpp void join(int x,int y) { int rootx=root(x),rooty=root(y); if (rootx==rooty) { //printf("加了就不是树了！！！"); return ; } access(x); beroot(y);//变成根 splay[y].pf=x;//接上x和y return ; } ``` 5.取出某条路径 x 到 y 的所查询权值 首先这条路径要有( root(x)==root(y) )！( ps: 在程序中我不会给出) 按照常理，我们先求LCA 先 access(x) 再 access(y) 将 x 所在preferred path的path father找出来，就是LCA 如果没有path father，则为 x 与 y 之间的一个 如果LCA就是根，那么只需 access(x) 、 access(y) 即可 否则我们先 access(x) ，再 access( LCA的父亲 ) 那么LCA所在preferred path就是 x 到LCA的路径 y 类似 计算的时候别忘了对LCA的重复判断 代码 ```cpp int LCA(int x,int y) { access(x); access(y); splay(x); splay(y);//注意一下splay是放在两个access后 if (splay[x].pf) return deep[x]<deep[y]?x:y;//深度小的是LCA else return splay[x].pf; } int find(int x,int LCA) { access(x); access(father(LCA)); splay(LCA);//把LCA变成所在路径的根 return splay[LCA].所需权值; } ``` 等等！ 思考如下方法： 我们先将 x 变成整棵树的树根 再 access(y) 如果是有根树我们在做完操作之后再把根变回去 这样，LCA就被我们完美避开了 代码： ```cpp int find(int x,int y) { beroot(x); access(y); splayup(y); return splay[y].所需权值; } ``` 突然一下简洁了许多！(^o^)/~ 程序不就是追求这个么？ 好了，到这里基本的LCT你其实已经会了Y(^o^)Y 在练手之前，我提醒一下几点： 1.注意这颗splay是带区间翻转操作的 2.如果维护的值较多，请仔细理清权值之间的关系并且固定好顺序 嗯，练手题： spoj 375 QTREE 这题是出了名的 维护一棵树支持两个操作 1.改变第 i 条边的权值 2.询问 a 到 b 的路径上的边权最大值 ( ps: spoj上的QTREE系列题目都可以做一做) 山东省选2008 洞穴探测cave 维护一棵树支持三个操作 1.在 x 和 y 之间连一条边 2.将 x 与 y 的连边断开 3.询问 x 与 y 是否联通 输入数据保证操作合法 hdu4010 维护一棵树支持四个操作 1.在 x 与 y 之间连一条边 2.将 x 作为根，然后断开 y 与父亲的连边 3.将 x 到 y 的路径上所有点点权 +k 4.询问 x 到 y 的路径上的点权最大值 每次操作若不合法请输出 −1 如果你能一遍A这三题，说明你的LCT已经上路了(๑´ㅂ`๑) 一点使用技巧 一、边权的维护技巧 之前的题目都没有涉及到边权啊，失误失误(⊙o⊙)！ 关于边权的维护，很多人会这么想： 反正一颗节点为 w 的树最多就 w−1 条边 嗯，除了根之外，其他的点全部捆绑上自己与父亲的连边进行维护 多么简单？ 一点也不好么╮(╯\_╰)╭ 如果你去写写你就知道了 access 会出大问题 1.path parent的修改会涉及到这条边的边权 2.当一条preferred path的根并不是这条链的顶端的时候，你会发现这个根绑定的权值和它的path parent的权值都需要维护(稍微不小心就会写错) 3.如果你不相信，你可以自己去实现实现，如果有简单的实现代码，请务必拿来让我膜拜一下/Orz 如果 access 出了问题，那么整个LCT就变得不好了╮(╯﹏╰）╭ 嗯，其实我一开始也不知道怎么改进，后来我膜拜了其他Orz的代码 “把一条边拆成一个点，然后按照点维护不就好了么(ーー゛)？”大神这么说 怎么就这么机智呢？还是要Orz一下 来道题练练手吧： NOI2014 魔法森林forest 在一个 n 个点的无向图上，每条边 i 有两个边权 ai,bi 请你找出一条从 1 到 n 路径，使得两个权值的最大值之和最小 啥？这真的是动态树(O\_O)？ 博主你在逗我吧？ 嗯(⊙v⊙)，这真的是动态树(虽然大牛们说自己都是写的spfa(ˇˍˇ）) 思考如下做法： 1.我们按照某一个边权 a 从小到大排序，将其依次加入图中 2.如果两点不连通，则直接加入 3.如果两点连通，则将两点原本的路径上的边权 b 最大的边找出来，然后与新加的边比较，如果新边较大，则不加，否则就把找出来的边删除，然后加入新边 4.如果成功加入某条边之后 1 与 n 联通，则统计答案 算法的思想大致如下： 总之就是按照 a 的边权排个序，轮流加入，维护图的边权b的最小生成树 很贪心对不对？ 为什么能贪心呢？ 你的问题实际上等价于：为什么 kruskal 算法是对的 这个证明满大街都是，如果你会拟阵则更方便 (UOJ上你是可以看到AC的代码的，你可以膜拜，如果发现问题你也可以hack，嗯，总之UOJ大法好) 二、动态无向图的连通性维护 先来看道题： 上海省选2008 堵塞的交通traffic 题意我就不解释了，因为我并不会讲(这题正解是线段树) 考虑变式题，如果是一个无向图，这该怎么实现连通性的维护呢？ 其实很简单 我们离线思考这个问题就会发现: 如果某个时刻两个点之间有多条路径，我们只需维护被破坏时间较后的那条路就可以了 也就是边权被破坏时间的最大生成树 嗯~(≧▽≦)/~，就是这样 如何维护最大生成树可以参考魔法森林的维护方法 妈妈如果我想维护最短路怎么办(=@\_\_@=)？ 这个……动态树真的可以做么(其实我也不知道)？ 说不定要用到更高端的数据结构，说不定根本就不行 谁知道呢？ (翱犇告诉我：洗洗睡吧，好像没有有竞赛价值的做法) 一点总结 解决动态树的东西肯定是不止LCT这一个东西的，还有ETT(Eular-Tour Tree) 那么为什么非要讲这个呢？ 当然是因为LCT是最容易实现的，也足够应付大部分动态树的题目了 额(⊙o⊙)… 如果你还不满足自己在动态树上的造诣的话 你可以去看看翱犇2014年的集训队论文《浅谈动态树的相关问题及简单拓展》(网上有2014集训队论文捆绑版) 如果你知道什么是仙人掌，你也可以去膜拜膜拜VFleaKing大神，并思考思考动态仙人掌(这个在UOJ和BZOJ上都有) 留下一个思考题吧，如果我们在对路径的权值修改操作的同时，加上对子树的权值修改操作，怎么办呢？