Self-Adjusting Top Tree 学习笔记
cancan123456
·
·
个人记录
参考资料 1
参考资料 2
一、SATT 能干什么？
它可以维护一个森林，支持如下操作：
-
加入/删除边，需要保证操作前后都是森林。
-
路径修改，路径查询，子树修改，子树查询。
举个例子？P5649 Sone1。
二、SATT 怎么干？
使用树收缩。
我们定义两种操作：\operatorname{Compress}(v),\operatorname{Rake}(v)，例子：
显然，\operatorname{Compress}(v) 消除一个度为 2 的节点，\operatorname{Rake(v)} 消除一个度为 1 的节点。在进行 \operatorname{Compress}(v) 后，我们将 v 的信息、uv 的信息和 vw 的信息放到 uw 中存储。在进行 \operatorname{Rake}(v) 后，我们将 v 的信息、vx 的信息放到 xw 中存储。
感性理解一下，我们可以将一棵树收缩成一条边和两个点，比如某论文中的例子：
再次感性理解，在收缩过程中一条边存储了原树中一个连通块，比如原树中 im 这条边就存储了 i,m,o,k 的导出子图。
我们将这样的子图称作树簇 \text{cluster}，显然至多两个节点和原树的其他节点项链，这两个节点称作界点 \text{boundary node}，其他在树簇中的店称作内点 \text{internal node}，两个界点之间的路径称作簇路径 \text{cluster path}。