Link-Cut Tree（LCT，动态树）

What · 是什么

LCT 用一组 Splay（辅助树）维护动态森林。原树被『实链剖分』为若干条实链（preferred path），每条实链放进一棵 Splay 中，Splay 的中序遍历对应原树上从上到下的一条链；每棵 Splay 的根通过虚边（认父不认子）指向其链顶在原树中的父节点。核心操作 access(x) 把 x 到根的路径暴露成一条实链（放进一棵 Splay），其余一切操作（makeroot 换根、link 连边、cut 删边、split 提取路径、findroot 求连通块根）都由若干次 access + splay 组合而成。所有基于 access 的操作均摊 O(log n)。

Why · 为什么

How · 实现

伪代码

struct LCT:
    ch[0..n][2], fa[0..n], rev[0..n], sum[0..n], val[0..n]

    isroot(x):  return ch[fa[x]][0] != x and ch[fa[x]][1] != x
    pushup(x):  sum[x] = sum[ch[x][0]] + val[x] + sum[ch[x][1]]
    pushrev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= 1
    pushdown(x): if rev[x]: pushrev(ch[x][0]); pushrev(ch[x][1]); rev[x]=0

    rotate(x):  # 经典 splay 旋转，注意 isroot 判断
    splay(x):   # 先下放路径上的翻转标记，再双旋

    access(x):
        last = 0
        while x:
            splay(x)
            ch[x][1] = last     # 实边切到 last，原右儿子变虚边
            pushup(x)
            last = x
            x = fa[x]           # 沿虚边向上
        return last

    makeroot(x): access(x); splay(x); pushrev(x)
    findroot(x):
        access(x); splay(x)
        while ch[x][0]: pushdown(x); x = ch[x][0]
        splay(x); return x
    split(x, y): makeroot(x); access(y); splay(y)   # 此时 y 子树即路径
    link(x, y):  makeroot(x); fa[x] = y             # 需判连通
    cut(x, y):   makeroot(x); access(y); splay(y)
                 # ch[y][0]==x 且 ch[x][1]==0 才合法，然后置零

Python 实现

class LinkCutTree:
    """教学实现：点权路径异或和（可改为 sum/max）。
    节点编号 1..n。
    """
    def __init__(self, n, val):
        self.n = n
        self.ch = [[0, 0] for _ in range(n + 1)]
        self.fa = [0] * (n + 1)
        self.rev = [0] * (n + 1)
        self.val = [0] + val[:]
        self.sum = [0] * (n + 1)
        for i in range(1, n + 1):
            self.sum[i] = self.val[i]

    def _isroot(self, x):
        f = self.fa[x]
        return f == 0 or (self.ch[f][0] != x and self.ch[f][1] != x)

    def _pushup(self, x):
        self.sum[x] = self.sum[self.ch[x][0]] ^ self.sum[self.ch[x][1]] ^ self.val[x]

    def _pushrev(self, x):
        self.ch[x][0], self.ch[x][1] = self.ch[x][1], self.ch[x][0]
        self.rev[x] ^= 1

    def _pushdown(self, x):
        if self.rev[x]:
            self._pushrev(self.ch[x][0])
            self._pushrev(self.ch[x][1])
            self.rev[x] = 0

    def _rotate(self, x):
        y, z = self.fa[x], self.fa[self.fa[x]]
        c = self.ch[y][1] == x
        b = self.ch[x][c ^ 1]
        if not self._isroot(y):
            self.ch[z][self.ch[z][1] == y] = x
        self.fa[x] = z
        self.ch[y][c] = b
        if b:
            self.fa[b] = y
        self.fa[y] = x
        self.ch[x][c ^ 1] = y
        self._pushup(y)
        self._pushup(x)

    def _splay(self, x):
        st = [x]
        y = x
        while not self._isroot(y):
            y = self.fa[y]
            st.append(y)
        for v in reversed(st):
            self._pushdown(v)
        while not self._isroot(x):
            y, z = self.fa[x], self.fa[self.fa[x]]
            if not self._isroot(y):
                if (self.ch[y][1] == x) == (self.ch[z][1] == y):
                    self._rotate(y)
                else:
                    self._rotate(x)
            self._rotate(x)

    def access(self, x):
        last = 0
        while x:
            self._splay(x)
            self.ch[x][1] = last
            self._pushup(x)
            last = x
            x = self.fa[x]
        return last

    def makeroot(self, x):
        self.access(x)
        self._splay(x)
        self._pushrev(x)

    def findroot(self, x):
        self.access(x)
        self._splay(x)
        while self.ch[x][0]:
            self._pushdown(x)
            x = self.ch[x][0]
        self._splay(x)
        return x

    def split(self, x, y):
        self.makeroot(x)
        self.access(y)
        self._splay(y)
        return self.sum[y]

    def link(self, x, y):
        self.makeroot(x)
        if self.findroot(y) != x:
            self.fa[x] = y

    def cut(self, x, y):
        self.makeroot(x)
        self.access(y)
        self._splay(y)
        if self.ch[y][0] == x and self.ch[x][1] == 0:
            self.ch[y][0] = 0
            self.fa[x] = 0
            self._pushup(y)

    def connected(self, x, y):
        if x == y:
            return True
        self.makeroot(x)
        return self.findroot(y) == x

if __name__ == '__main__':
    n = 5
    val = [1, 2, 3, 4, 5]
    lct = LinkCutTree(n, val)
    # 建树: 1-2, 1-3, 3-4, 3-5
    lct.link(1, 2)
    lct.link(1, 3)
    lct.link(3, 4)
    lct.link(3, 5)
    assert lct.connected(2, 5)
    print('path 2..5 xor =', lct.split(2, 5))
    assert lct.split(2, 5) == (2 ^ 1 ^ 3 ^ 5)  # 2-1-3-5
    # 换根后查询不同路径
    lct.makeroot(4)
    assert lct.split(4, 1) == (4 ^ 3 ^ 1)
    # 删边 1-3，断开 1 与 3/4/5
    lct.cut(1, 3)
    assert not lct.connected(1, 4)
    assert lct.connected(3, 5)
    print('OK')

易错点

• isroot 用 fa 判断而不用『儿子是否为 x』，否则虚边方向错误
• _rotate 中必须先判断 y 是否 isroot 再改 z 的儿子，否则破坏辅助树
• splay 前必须把祖先链上的 rev 标记按序下放，否则翻转错位
• makeroot 的 rev 标记会反转路径，查询路径前要先 pushdown 再取信息
• cut 必须先验证 ch[y][0]==x 且 ch[x][1]==0（x 与 y 直连）才断开
• 节点编号从 1 开始，0 号节点的 fa/ch 恒为 0，isroot(0) 需特判
• access 里要 pushup(x)，忘记更新 sum 是常见 WA 源

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/lct.md
• OI Wiki✓ https://oi-wiki.org/ds/lct/