简明 TopTree 指南

· · 个人记录

前言:@杀光 ds 怪 大哥你这么会 top tree 啥时候能不能写个教程造福一下没有学习能力的人 wuwu

簇

簇的性质

一个簇是一个连通的边集,并且最多只有两个点有不在簇内的边,即最多只有两个点连向簇外。

我们称这些点为界点,如果这样的点不足两个,剩下的界点可以根据习惯钦定。

两个界点之间的边为簇路径。

在按照下文所说的方法构造的 top tree 中,簇还有一些其它性质。以下这些性质可以更好地刻画簇的形象,但是它们并不必要。

簇内所有边的端点中,最浅的点是界点,我们称之为上界点。如果存在非最浅点连向簇外,我们称之为下界点,否则任意钦定一个叶子作为下界点均合法。

如果某个簇的上界点 u 有儿子 v,若边 (u,v) 在簇内,v 子树内的所有边均在簇内。

如果某个簇簇路径上有点 u,u 不为界点,u 的儿子 v 不在簇路径上,则 v 子树内所有边均在簇内。

簇的合并

类比相邻的两个区间能够合并成一个区间,有相同点作为界点的两个簇也能够合并。簇的合并分为两种:compress 和 rake。

当簇 A 的下界点和簇 B 的上界点相同时可以 compress,合并后的簇,上界点为 A 的上界点,下界点为 B 的下界点。

当簇 A,B 的上界点相同,并且 B 下界点没有儿子时,可以 rake,合并后的簇,上界点为 A,B 的上界点,下界点为 A 的下界点。

注意 rake 后 B 原有的下界点不再为界点,为了让合并后的簇合法,B 的下界点不能连向簇外。

有了这两种合并,一棵树初始每个边各自成簇,一定存在某种合并方式,将所有簇最终合并成包含所有边的“根簇”。

compress 和 rake 合并信息的方式往往是不同的,需要分开实现。

信息的维护模式

最大权独立集

【模板】"动态DP"&动态树分治(加强版)

分别维护簇内独立集不包含两个节点、只包含上界点、只包含下界点、两个节点均包含的最大权值。

注意这里的权值不考虑界点。否则界点会被多个簇同时包含,修改时需要更改多个簇的信息,并且可能导致重复统计。不过在某些问题中可以改成统计下界点,但不统计上界点,可以更方便地处理,并且获得更小的时间空间常数。

树上距离最近/远关键点

[ZJOI2007] 捉迷藏、[CEOI2019] Dynamic Diameter

分别维护簇路径的长度、距离上界点最近/远的点到上界点的距离、距离下界点最近/远的点到下界点的距离、簇内(不包含两个界点)两两点的最短距离。

邻域信息和

【模板】点分树 | 震波

分别维护簇内到两个界点距离最远的点到该界点的距离 p,q,和距离不超过 1,2,3,\cdots,p-1(或 q-1)的所有点的信息和。这样合并两个簇的复杂度为 O(\mathrm{size}),其中 \mathrm{size} 为簇的大小。

为了保证单点修改的复杂度,需要线段树/树状数组来维护。