lg树上操作
- P3258
树上差分
- P1600 [NOIP2016] 天天爱跑步
分开两边处理。
对于上升段，如果一个点深度是 x=dep_i+w_i ，那么 i 就被贡献
我们可以将整个上升段的 x 位置都加，然后在每个点处统计 dep_i+w_i 位置的值。每个点开一个 vector 记录修改操作。不过这样可能会有互相影响的问题，但是鉴于我们只关系一个位置即 dep_i+w_i，我们可记录这个值的变化量。
下降段同理。
- DFN
子树修改
这样的话，出现这种情况的次数就是 \(\mathcal O(\log n)\)
- slpf
请注意重链剖分的 dfn 序也满足上面的性质。
- 转化：寻找影响了哪些节点的思路
P4092 树 --- 转化为子树取 max
由于是单点查询，不需要 segment beats，可以用标记永久化。
成功减小复杂度。
- 轻重儿子分开维护
- P5305 [GXOI/GZOI2019] 旧词
去除限制：离线排序处理
范围是小于等于，考虑排序离线去除限制。
若 y 是 v 的重儿子，那么所有 x 对 v 的贡献就是维护的值，否则单独进行贡献，进行一个子树求和。这样大开销的子树求和就不会进行很多次。
而对于插入点的操作，只有走轻边的时候才会修改。
利用的就是 1. 重儿子是唯一的 2. 跳轻边的时候是少的
通常都是维护轻儿子信息。
- 长链剖分
重儿子改成深度最大的儿子。称长儿子
-
一个点的 k 级祖先所在的长链长度至少为 k
-
u 所在的长链比其短儿子所在的长链长，故 u 到根上的轻边数量是 \(\sqrt n\) 级别的
- 树上 k 级祖先
这样虽然预处理的时间是和树上倍增一样的，但是它每次查询都是 \(\mathcal O(1)\) 的
-
CF1009F
-
树上启发式合并 dsu on tree
若求出 x 的答案可以调用 Solve(x)
则 Solve(x) 的工作流程如下
-
对每个轻儿子调用 Solve（下面过程5会将其清空）
-
对每个重儿子调用 Solve（不会被清空）
-
暴力加入轻儿子及其子树对 x 的贡献
-
记录 x 的答案
-
如果 x 自己是父亲的轻儿子，则清空所有答案
这样就保证时刻存储的都是自己子树的信息。
时间是 \(\mathcal O(n\log n\times T(n))\) \(T(n)\) 是一次修改的复杂度。
- CF600E
模板
- 点分治
对一棵树，找到一个点 u，处理所有经过点 u 的路径的信息。
然后把树分成若干部分，然后对于每一个部分继续上述操作，则我们要使得分出的最大部分尽可能小，每一部分都不超过总数的二分之一，这样递归只需要 log 次。
- P3806 模板点分治
只要考虑计算出如何统计经过点 u 的信息，考虑拼接。
依次扫描每一棵子树，统计有多少深度为 l 的路径，与之前子树存储的进行拼接。
- 构造一个点集，使得树上所有长度不超过 k 的路径都被覆盖至少一次。
- 动态点分治/点分树
将点分治的结构存储下来，这样就成为一棵高度为 log 的树。
如果修改一个节点，那么祖先节点都会发生变化。
- P6329 模板点分树
对这个结构维护若干线段树。查询的时候就跳祖先查询，修改的时候跳祖先修改即可。
- 虚树
最简单的方式就是关键点之间两两求 LCA
不过，根据 DFN 的性质，只需要求两两相邻的 LCA 即可
我喜欢的方法：
性质：如果一个点本身不是关键点，那么它至少有两个儿子。所以总共节点数目不超过 2m
- 典中点 消耗战