水平不高, 内容比较简单.
内容难度不随章节单增.
0. 杂七杂八
做题做到什么东西都会扔到这里. 想到啥写啥.
-
如果要求统计树上所有点对之间的贡献, 可以考虑枚举 lca. (CF1856E1)
-
如果有类似于树上经过的边的权值 \(\leq k\) 这样的限制, 可以把边按照边权排序再往里面加. 要求是能快速算出把两个连通块连起来的贡献. (CF1857G)
-
如果所有询问都是从根到一个结点这样的, 可以直接在 dfs 时维护加入/撤销. (AT_abc302_h)
-
把一些点连起来的最小连通块: 利用虚树结论, 维护 dfs 序相邻的点, 但是写起来简单地多. (CF176E)
-
中途换根对子树和 lca 的影响: 分类讨论即可. (CF916E)
1. 重链剖分
用于路径/子树的修改询问.
大致思路是, 尝试用线段树来维护 dfs 序. 子树是容易的.
对于链, 如果能够让 dfs 序连续, 那也是容易的. 为了尽可能做到 dfs 序的连续, 我们每次先 dfs 重儿子, 这样形成若干条重链. 因为到根的路径可以拆成 \(O(\log n)\) 条重链, 该算法时间复杂度正确.
(过于简单, 不给例题了)
2. 树上线段树合并
直接上题目.
例 1: P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
例 2: P6773 [NOI2020] 命运
3. dsu on tree / 树上启发式合并
不带修子树询问.
4. 长链剖分
这个东西可以 \(O(n\log n)-O(1)\) 求树上 k 级祖先, 不过用处不大.
比较重要的是, 长链剖分可以用来优化只与深度有关的 dp.
例 1: CF1009F Dominant Indices
例 2: P5904 [POI2014] HOT-Hotels 加强版
例 3: P4292 [WC2010] 重建计划
5. 点分治
一般用来统计路径.
具体操作是, 选定一个点 (树的重心), 一次做完所有经过这个点的路径, 然后只需到各个子树继续统计.
例 1: P4178 Tree
简单题. 使用点分治, 直接考虑怎么统计经过一个点的路径.
为了避免统计到两个点在一个子树里的情况, 我们可以对每棵子树, 先查它的贡献, 再加进去.
于是直接 dfs 求深度, 用个树状数组统计一下就完事了.
时间复杂度 \(O(n\log n\log k)\).
例 2: CF293E Close Vertices
实际上还有边分治这样的东西, 原理差不多, 并且只会出两个子树, 比较好讨论. 但是边分需要三度化, 很难写.
6. 单侧点分治
名字是随便起的. 直接看题.
例 1: P4886 快递员
例 2: CF566C Logistical Questions
7. 点分树
8. 虚树
用于每次询问和点集有关的问题, 这时需要一个只与点集大小相关的算法而不需要原来的树.
方法是一开始求出来每个点的 dfs 序, 然后询问的时候, 把相邻两个点的 lca 拉出来建树 (结论). 然后对着建出来的虚树进行操作即可.