简明 TopTree 指南
前言:@杀光 ds 怪 大哥你这么会 top tree 啥时候能不能写个教程造福一下没有学习能力的人 wuwu
簇
簇的性质
一个簇是一个连通的边集,并且最多只有两个点有不在簇内的边,即最多只有两个点连向簇外。
我们称这些点为界点,如果这样的点不足两个,剩下的界点可以根据习惯钦定。
两个界点之间的边为簇路径。
在按照下文所说的方法构造的 top tree 中,簇还有一些其它性质。以下这些性质可以更好地刻画簇的形象,但是它们并不必要。
簇内所有边的端点中,最浅的点是界点,我们称之为上界点。如果存在非最浅点连向簇外,我们称之为下界点,否则任意钦定一个叶子作为下界点均合法。
如果某个簇的上界点
如果某个簇簇路径上有点
簇的合并
类比相邻的两个区间能够合并成一个区间,有相同点作为界点的两个簇也能够合并。簇的合并分为两种:compress 和 rake。
当簇
当簇
注意 rake 后
有了这两种合并,一棵树初始每个边各自成簇,一定存在某种合并方式,将所有簇最终合并成包含所有边的“根簇”。
compress 和 rake 合并信息的方式往往是不同的,需要分开实现。
信息的维护模式
最大权独立集
【模板】"动态DP"&动态树分治(加强版)
分别维护簇内独立集不包含两个节点、只包含上界点、只包含下界点、两个节点均包含的最大权值。
注意这里的权值不考虑界点。否则界点会被多个簇同时包含,修改时需要更改多个簇的信息,并且可能导致重复统计。不过在某些问题中可以改成统计下界点,但不统计上界点,可以更方便地处理,并且获得更小的时间空间常数。
树上距离最近/远关键点
[ZJOI2007] 捉迷藏、[CEOI2019] Dynamic Diameter
分别维护簇路径的长度、距离上界点最近/远的点到上界点的距离、距离下界点最近/远的点到下界点的距离、簇内(不包含两个界点)两两点的最短距离。
邻域信息和
【模板】点分树 | 震波
分别维护簇内到两个界点距离最远的点到该界点的距离
为了保证单点修改的复杂度,需要线段树/树状数组来维护。