Top Tree（Self-Adjusting Top Tree，SATT）

What · 是什么

Top Tree 是一棵二叉树，每个节点对应原树在树收缩过程中的一个『簇』（Cluster）——一个由 Compress/Rake 操作合并出来的连通子图，有两个端点。叶子是基簇（单条边），根是根簇（除端点外包含整棵树）。Self-Adjusting Top Tree（SATT）由 Tarjan 与 Werneck 于 2005 年提出，用一棵自调整三叉树（Compress Tree + Rake Tree 组合）表示簇的层级关系，支持链修改/查询、子树修改/查询，以及非局部搜索（如动态维护重心、直径）。

Why · 为什么

How · 实现

伪代码

struct SATT:
    # 三叉树：ls/ms/rs，节点类型 op ∈ {Compress, Rake}
    len[x]      # Compress 簇路径长度
    maxs[x][0/1] # 簇端点到簇内点/端点的最大距离（Rake 只用 maxs[0]）
    diam[x]     # 簇直径

    Pushup(x):
      if op[x] == Compress:
        len[x] = len[ls]+len[rs]
        diam[x] = max(maxs[ls][1]+maxs[rs][0],
                      max(maxs[ls][1],maxs[rs][0])+maxs[ms][0],
                      max(diam[ls],diam[rs],diam[ms]))
        maxs[x][0]=max(maxs[ls][0], len[ls]+max(maxs[ms][0],maxs[rs][0]))
        maxs[x][1]=max(maxs[rs][1], len[rs]+max(maxs[ms][0],maxs[ls][1]))
      else:  # Rake
        diam[x] = max(maxs[ls][0]+maxs[rs][0],
                      maxs[ms][0]+max(maxs[ls][0],maxs[rs][0]),
                      max(diam[ls],diam[rs],diam[ms]))
        maxs[x][0]=max(maxs[ms][0], max(maxs[ls][0],maxs[rs][0]))

    Access(x):  # 把 x 旋到全局根（省略 Global Splay 细节）
    Link/ Cut/ PathQuery/ SubtreeQuery: 均基于 Access + Pushup

Python 实现

import random

class SATTNode:
    """简化教学实现：仅用于展示簇树的 Pushup 结构，非完整 SATT。
    真实 SATT 需三叉自调整结构与 Access 序列，Python 实现过于复杂，
    本节点以概念演示为主，详见 OI Wiki top-tree 页面。"""
    __slots__ = ('op', 'left', 'mid', 'right', 'len', 'maxs', 'diam')
    def __init__(self, op):
        self.op = op  # 'compress' | 'rake'
        self.left = self.mid = self.right = None
        self.len = 0
        self.maxs = [0, 0]
        self.diam = 0

def pushup(x):
    """演示 Compress/Rake 节点的信息合并（OI Wiki 代码的 Python 直译）"""
    L, M, R = x.left, x.mid, x.right
    if x.op == 'compress':
        x.len = (L.len if L else 0) + (R.len if R else 0)
        ms0 = M.maxs[0] if M else 0
        ms1 = M.maxs[0] if M else 0
        dl = L.diam if L else 0
        dr = R.diam if R else 0
        dm = M.diam if M else 0
        x.diam = max((L.maxs[1] if L else 0) + (R.maxs[0] if R else 0),
                     max((L.maxs[1] if L else 0), (R.maxs[0] if R else 0)) + ms0,
                     max(dl, dr, dm))
        x.maxs[0] = max((L.maxs[0] if L else 0),
                        (L.len if L else 0) + max(ms1, (R.maxs[0] if R else 0)))
        x.maxs[1] = max((R.maxs[1] if R else 0),
                        (R.len if R else 0) + max(ms0, (L.maxs[1] if L else 0)))
    else:  # rake
        ls0 = L.maxs[0] if L else 0
        rs0 = R.maxs[0] if R else 0
        ms0 = M.maxs[0] if M else 0
        x.diam = max(ls0 + rs0, ms0 + max(ls0, rs0),
                     max(L.diam if L else 0, R.diam if R else 0, M.diam if M else 0))
        x.maxs[0] = max(ms0, max(ls0, rs0))

def top_tree_selfcheck():
    # 单节点叶簇：压缩路径长度为边权，构造一条三边链并验证 len 与直径
    a = SATTNode('compress'); a.len = 2; a.maxs = [2, 2]
    b = SATTNode('compress'); b.len = 3; b.maxs = [3, 3]
    root = SATTNode('compress')
    root.left, root.right = a, b
    pushup(root)
    assert root.len == 5
    assert root.diam == 5
    print('TopTree cluster pushup OK (len=%d diam=%d)' % (root.len, root.diam))

if __name__ == '__main__':
    top_tree_selfcheck()

易错点

• Compress 与 Rake 节点的 Pushup 公式不同，写反导致信息错误
• SATT 的三叉结构顺序（ls/ms/rs）决定簇路径方向，翻转时必须交换 ls/rs 与 maxs[0/1]
• 非局部信息（如重心、第二小）不能只靠 Pushup，需在簇树上搜索，勿直接用子树聚合
• 省略 Global Splay 会影响均摊界，测试数据小可能看不出来
• 先完整掌握 LCT 与动态树再学 SATT，直接上手极易出错

例题

信源

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