Link Cut Tree

Hardsoft

2026-01-22

学习记录

动态树

LCT, $\text{Link-Cut-Trees}$，顾名思义就是支持增加和删除树上的一条边的数据结构。这个算法有着和 Splay 一样优异的均摊时间复杂度，每一次访问都会让树伸展得更加 elegant。

一、核心思想

使用一颗平衡树来维护树上的一条链。多个链使用朴素方法连接起来，就得到了 LCT。

二、具体思路

假设我现在要维护一颗动态树，他是无根的。我现在想访问两点 $(u,v)$ 之间的一条简单路径，统计这条路径上的信息（如果是链平衡树可以做），我应该怎样处理？

LCT 是这样做的：
首先目前树上有很多条链。根据一个 $map$ 直接找到两个点对应的链。然后，将一个点一直到根的链连接形成一个平衡树（除链上的点外可以断开），另外一个也是的。最后对其中一个做一个区间反转，再将两个合并，就可以了。
```
    flowchart TD
 classDef red stroke:red
 classDef cyan stroke:cyan
 classDef green stroke:green
 subgraph BEF[ ]
   direction TB
   subgraph CH0[ ]
     direction LR
     A1( ) -.- A(root) -.- A3( )
   end
   subgraph CH2[ ]
     direction LR
     C1( ):::cyan -.- C([v]):::red -.- C3( )
   end
   subgraph CH1[ ]
     direction LR
     B1( ) -.- B([u]):::red -.- B3( ):::green
   end
   CH0 -..-> CH1
   CH0 -..-> CH2
 end
 subgraph AFT[ ]
   direction TB
   subgraph CH3[ ]
     Aa( ) -.- BB(u):::red -.- AA(root) -.- CC(v):::red -.- Ab( )
   end
   subgraph CH4[ ]
     Ba( ) -..- Bb( )
   end
   subgraph CH5[ ]
     Ca( ) -..- Cb( )
   end
   CH3 -..-> CH4
   CH3 -..-> CH5
 end
 BEF --> AFT
```
（这里只是举了个例子，不一定是二叉树哦）
这是最最最最核心的了，但是可能维护这样一个随时断开、合并的动态链树还是有一些困难。介绍一种思想，也是整个 LCT 最难以理解的一个点。

认父不认子

这个一讲就懂了。在 Splay 中，我们不是要维护一个节点 $u$ 的 $fa$ 嘛，如果 $fa$ 有 $ch_{0/1}=u$，那就是 $u$ 不是 Splay 的根节点。否则，$u$ 是 Splay 的根节点，并且他的 $fa$ 实际上记录了原树当中的 $fa$。也就是，可以写一个 isroot。
1
inline bool isroot(int u) { return U(FA)[L] != u && U(FA)[R] != u; }
如果有 isroot(u) 为真那么 U[FA] 就是可信的。否则就是虚的，是我们构造的 Splay 中的 $fa$。

三、实现

inline int access(int u) {
    int p = 0;
    for (; u; p = u, u = U[FA])
        splay(u), U[R] = p, pushup(u);
    return p;
}
inline int getroot(int u) {
    for (u = access(u); U[L]; u = U[L]) pushdown(u);
    return splay(u), u;
}
inline void changeroot(int u) { access(u), splay(u), reverse(u); }

其实就这三个函数够用了，一个访问 $u$ 拎出来 $u\to root$ 的信息，一个能获取树根，一个能更改树的根。
再注意一下 rotate 和 splay 中的细节，要用 isroot。

void sync(int u) { if (!isroot(u)) sync(U[FA]); pushdown(u); }
inline void rotate(int u) {
    bool tp = type(u);
    int fa = U[FA], anc = U(FA)[FA];
    if (!isroot(fa)) tr[anc][type(fa)] = u;                 // 注意
    tr[fa][tp] = U[!tp]; if (U[!tp]) U(!tp)[FA] = fa;
    U[!tp] = fa; tr[fa][FA] = u; U[FA] = anc;
    pushup(fa), pushup(u);
}
inline void splay(int u) {
    sync(u);
    for (; !isroot(u); rotate(u))                           // 注意
        if (!isroot(U[FA]))
            rotate(type(u) == type(U[FA]) ? U[FA] : u);
}

一、核心思想

二、具体思路

认父不认子

三、实现