Link-cut Tree,简称 LCT。
干什么的?它是树链剖分的升级版,可以看做是动态的树剖。
树剖专攻静态树问题;LCT 专攻动态树问题,因为此时的树剖面对动态树问题已经无能为力了(动态树问题通常夹杂着树的操作,如删边与连边。这是线段树无法应对的)。
LCT 难写吗?不难写啊!真的没有 200 行......
让我们用简洁的写法来搞定 LCT:只需要一些基础函数,再疯狂调用这些函数就好啦。
树链剖分把树分成若干条重链,对于每条重链,用线段树来维护信息。利用各线段树的信息来得到答案。
模仿一下:
这是假的重链!树剖是挑选重儿子来延续重链;而 LCT 的重链是随缘的......
我们先不管这里的重链是怎么确定的,因为在 LCT 中,重链是可以随时更改的!(不要畏惧更改操作,一切都可以用基础函数的简单调用搞定)
LCT 是怎么存储的?
很简单,我们不要把树看成树剖一样的形式,分开若干条重链用线段树维护,又拼起来。
我们的每条重链的 Splay,都是连在一起的,但又是相互独立的!看图:
橙色边为每棵 Splay,灰色边表示的是 Splay 之间的连接边。
每棵 Splay 储存照常,Splay 的中序遍历即重链节点从浅到深的排列。每棵 Splay 内节点的关系可能和原树不同,但是与其他 Splay 连边的节点没有改变。
但只有每棵 Splay 的根节点能连向其他 Splay 的某个节点(灰色边)。Splay 根节点 $root$ 记录它的父亲是谁(有的 Splay 根节点 $root$ 没有父亲),而它的父亲并不记录自己有这个儿子 $root$。
发现,每一个节点,都能够通过一直走父亲,走到某一个点,这个点就是上节提到的根节点,不同于 Splay 的根节点。
- bool isSplayRoot(int u) {
- return ch[fa[u]][0] != u && ch[fa[u]][1] != u;
- }
即父亲的左右儿子都不是自己,说明此节点是 Splay 的根节点,它的父亲并不记录自己。
- int who(int u) {
- return ch[fa[u]][1] == u;
- }
如果是左儿子,返回 0;否则返回 1。
- void update(int u) {
- if (!u) return;
- inf[u] = max(w[u], max(inf[ch[u][0]], inf[ch[u][1]]));
- }
- void reverse(int u){
- rev[u]^=1;
- swap(ch[u][0],ch[u][1]);
- }
- //为u打上翻转标记
- void pushdownOnce(int u){
- if(rev[u]){
- if(ch[u][0]) reverse(ch[u][0]);
- if(ch[u][1]) reverse(ch[u][1]);
- rev[u]=0;
- }
- }
- //单次下传
- void pushdown(int u){
- if(!isroot(u)) pushdown(fa[u]);
- pushdownOnce(u);
- }
- //从当前Splay的根节点一路下传到u,把一路的翻转都处理掉
- void rotate(int u){
- int f=fa[u],g=fa[f],c=who(u);
- if(!isroot(f))
- ch[g][who(f)]=u;
- fa[u]=g;
- ch[f][c]=ch[u][c^1]; fa[ch[f][c]]=f;
- ch[u][c^1]=f; fa[f]=u;
- update(f); update(u);
- }
- //将当前节点u旋转到父亲节点
- void splay(int u) {
- pushdown(u);
- while (!isroot(u)) {
- if (!isroot(fa[u])) rotate(who(fa[u]) == who(u) ? fa[u] : u);
- rotate(u);
- }
- }
- //将u旋转到当前Splay的根节点
- void access(int u) {
- for (int v = 0; u; v = u, u = fa[u]) {
- splay(u);
- ch[u][1] = v;
- update(u);
- }
- }
什么意思呢?外层 for 循环负责迭代从 $u$ 一直到 Splay 根节点的路径,同时用 $v$ 记录是从哪里来到 $u$ 的。
每到达一个点 $u$,我们将 $u$ 提到树根,这时 $u$ 的右儿子就是在原本重链上 $u$ 的重儿子。我们把它替换成过来的节点,并更新信息即可。
- void makeRoot(int u) {
- access(u);
- splay(u);
- reverse(u);
- }
换根换根,实际上影响到的是哪些因素呢?
换根,仅仅是 $u$ 到 LCT 根节点一路上的信息发生了父子反向,对于其它的 Splay 并没有影响。
于是神奇的调用来了:
这样就为 $u$ 到根节点的信息完成了父子反向操作。
(我们之后可以慢慢体会到 LCT 的调用的巧妙和精美)
- void link(int a, int b) {
- makeRoot(a);
- fa[a] = b;
- }
我们将 $a$ 变为 $a$ 的 LCT 的根,然后将 $a$ 的父亲设为 $b$。这样就将 $a$ 的整棵 LCT 连接到了 $b$ 所在的 LCT。
- void cut(int a, int b) {
- makeRoot(a);
- access(b);
- splay(b);
- fa[a] = 0;
- ch[b][0] = 0;
- update(b);
- }
我们将 $a$ 变成 LCT 的根,然后将 $b$ 到 LCT 根节点(也就是 $a$)一路变为重链,再将 $b$ 旋转到所在 Splay 的根。
由于 $a$ 和 $b$ 同在一棵 Splay 中且 $a$ 一定是 $b$ 的父亲,所以 Splay 中 $b$ 的左儿子一定是 $a$,断开即可,记得更新,因为有了父子关系变化。
- bool isConnect(int a, int b) {
- if (a == b) return true;
- makeRoot(a);
- access(b);
- splay(b);
- return fa[a];
- }
我们将 $a$ 变成 LCT 的根,然后将 $b$ 到 LCT 根节点(也就是 $a$)一路变为重链,再将 $b$ 旋转到所在 Splay 的根。(怎么和上面很像呢哈哈)
如果 $a$ 和 $b$ 不在同一棵 LCT 中,执行 $makeRoot(a)$ 后,$a$ 的父亲应该为空($makeRoot$ 最后有一个 $splay(u)$ 的操作将 $u$ 旋转到树根)。
除非什么情况呢?除非 a 和 b 在同一棵 LCT 中,在 $access(b)$ 并 $splay(b)$ 后,$a$ 与 $b$ 应该在同一棵 Splay 中,既然 $b$ 为 Splay 根,那么 $a$ 肯定不为 Splay 根,$a$ 一定有一个父亲存在。
可以发现 $access(u)$ 和 $splay(u)$ 总是配套出现,有时在前面配上 $makeRoot$。这一套 COMBO 可以将 $u$ 转到 Splay 树根,然后进行如同 Splay 一样的便捷操作。
比如想求 $a$ 到 $b$ 的点权之和,我们可以 $makeRoot(a) + access(b) + splay(b)$,此时 $a$ 和 $b$ 一定在同一条重链、同一棵 Splay 中,然后我们统计 Splay 中 $b$ 和 $b$ 的左子树的点权之和就可以了。
久仰 LCT,总觉得特别难,但是理解以后就会觉得很有意思。一些处理信息、调用函数的思想,值得我们更多地推敲。
来源: http://www.cnblogs.com/RogerDTZ/p/7436469.html