by TheBigYellowDuck
重链剖分
取 preferred-son 为子树大小最大的儿子，是为重链剖分。
一条最重要的性质：每个点到根路径上的轻重边切换次数为 \(\log n\) 级别，也就是每经过一条轻边，子树大小至少除以二。这一点为很多基于重链剖分的暴力提供了复杂度保证。
P2486 [SDOI2011] 染色
一眼树剖。线段树维护区间颜色段数量和左右端点的颜色即可。
注意查询时有些细节。要额外记录一下从左向上跳的链顶的颜色和从右向上跳的链顶的颜色。
时间复杂度 \(\mathcal{O}(n \log ^2n)\)。
P6157 有趣的游戏
Key Observation：选取的 \(w_x\) 和 \(w_y\) 一定是链上的严格次大值和最大值。
A 的分数可以树剖，用线段树维护区间最大值和严格次大值即可。B 的分数是来自于整棵树的，一个 std::multiset 就可以维护了。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
懒得再写了，放一个远古的 提交记录
P7735 [NOI2021] 轻重边
关键在于以一种高效的方式判定轻重边。
一个点被修改后，只会连出一条重边，而这条重边也恰好被修改过了。也就是说，只有在同一时间被修改的边才会是重边。这提示我们考虑时间戳。
每次修改，对一条链打上一个新的时间戳，那么重边的判据为，其端点的时间戳相等。这样就将问题转化为了区间覆盖，维护区间颜色段相关信息。线段树即可。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。注意实现细节。
P4374 [USACO18OPEN] Disruption P
观察到断开某条树边之后，在不考虑非树边的情况下会形成两个连通块。若存在某条非树边连接两个连通块，则只需要花这一条边的代价就可以使得被断掉的两个顶点连通。
进一步说，断掉某条树边之后，答案即为连接两个连通块的所有非树边的最小值。
考虑一条非树边 \((u,v,w)\)，当断掉树上 \(u\) 到 \(v\) 路径上的树边时，答案一定不大于 \(w\)，也就是在树上 \(u\) 到 \(v\) 的路径上所有树边对 \(w\) 取 \(\text{min}\)。每条树边的答案只需要查单点的值即可。
区间取 \(\text{min}\) 不会做，怎么办？考虑把非树边按照边权从大到小排序，这样后面的修改一定会覆盖前面的修改。这样问题就变成了区间覆盖单点查询，用树剖维护即可。
时间复杂度 \(\mathcal{O}((n+m)\log^2n)\)。
P3313 [SDOI2014] 旅行
P3703 [SDOI2017] 树点涂色
P4211 [LNOI2014] LCA
P3979 遥远的国度
CF916E Jamie and Tree
CF1023F Mobile Phone Network
动态 DP
动态 dp 用来解决一些带修的 dp 问题，很多时候与树形结构结合。核心思想是用矩阵描述转移，线段树维护矩阵乘法，从而实现快速维护修改。
在树上应用时，通常与树链剖分结合，将轻链上的信息通过重链上的矩阵乘法维护。
P4719 【模板】动态 DP & 动态树分治
静态的 dp 是经典问题，设 \(f(i,0/1)\) 表示在点 \(i\) 的子树中，不选/选 \(i\) 的最大独立集。
\[f(i,0)=\sum_j\max\{f(j,0),f(j,1)\} \]\[f(i,1)=a_i+\sum_jf(j,0) \]为了带修，先将整棵树进行树链剖分，令 \(\text{son}_i\) 为 \(i\) 的重儿子。令 \(g(i,0/1)\) 表示不选/选 \(i\) 且不考虑重儿子子树的答案。假设我们已经有了 \(g\) 数组，那么有转移
\[f(i,0)=g(i,0)+\max\{f(\text{son}_i,0),f(\text{son}_i,1)\} \]\[f(i,1)=g(i,1)+f(\text{son}_i,0) \]考虑把转移套进矩阵，定义广义矩阵乘法
\[C_{i,j}=\max_k\{A_{i,k}+B_{k,j}\} \]把第一个式子的 \(g(i,0)\) 吃进 \(\max\) 里面，转移可以写成
\[\begin{bmatrix} g(i,0) & g(i,0) \\ g(i,1) & -\infty \end{bmatrix} \times \begin{bmatrix} f(\text{son}_i,0) \\ f(\text{son}_i,1) \end{bmatrix}= \begin{bmatrix} f(i,0) \\ f(i,1) \end{bmatrix}\]这样，修改操作时只需要修改 \(g(i,1)\) 的值，也就是改一个单点的矩阵。
树剖的同时预处理初始状态的 \(f,g\) 数组。\(g\) 数组的统计类似 \(f\)，只需要规避掉重儿子的贡献即可。
用线段树维护重链上的矩阵乘法，修改时从 \(i\) 向根节点跳重链，不断修改矩阵的值。查询的答案就是根节点到其重链底端的矩阵乘积。
时间复杂度 \(\mathcal{O}(n \log^2n)\)。
P6021 洪水
令 \(f(u)\) 表示在 \(u\) 子树中断掉所有叶子的最小代价。
\[f(u)=\min\left\{a_u,\sum_vf(v)\right\} \]由于带修，考虑 ddp。先树链剖分，令 \(\text{son}_u\) 表示 \(u\) 的重儿子。
记 \(g(u)\) 表示 \(u\) 子树中不考虑重儿子子树的答案。
\[f(u)=\min\{a_u,f(\text{son}_u)+g(u)\} \]把这个东西写成 \((\min,+)\) 矩阵，我们要添一个常数项。
\[\begin{bmatrix} g(u) & a_u \\ +\infty & 0 \end{bmatrix} \times \begin{bmatrix} f(\text{son}_u) \\ 0 \end{bmatrix} = \begin{bmatrix} f(u) \\ 0 \end{bmatrix}\]子树查询，其实也是一样的。只需要查 \(u\) 到其所在重链底端这一段的矩阵乘积就好了。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
P5024 [NOIP2018 提高组] 保卫王国
最小权覆盖集 = 全集 - 最大权独立集。钦定点选与不选可以通过把点权调成 \(\infty\) 实现。这样就完全转成了上面的模板题。直接搬过来就行了。
直接推 dp 式子也是可以的。令 \(f(i,0/1)\) 表示在点 \(i\) 的子树中，不选/选 \(i\) 的答案。
\[f(i,0)=\sum_jf(j,1) \]\[f(i,1)=a_i+\sum_j\min\{f(j,0),f(j,1)\} \]树链剖分，令 \(\text{son}_i\) 为 \(i\) 的重儿子。令 \(g(i,0/1)\) 表示不选/选 \(i\) 且不考虑重儿子子树的答案。
\[f(i,0)=g(i,0)+f(\text{son}_i,1) \]\[f(i,1)=g(i,1)+\min\{f(\text{son}_i,0),f(\text{son}_i,1)\} \]把矩阵乘法的运算换成 \((\min,+)\)，用矩阵写转移方程。
\[\begin{bmatrix} +\infty & g(i,0) \\ g(i,1) & g(i,1) \end{bmatrix} \times \begin{bmatrix} f(\text{son}_i,0) \\ f(\text{son}_i,1) \end{bmatrix}= \begin{bmatrix} f(i,0) \\ f(i,1) \end{bmatrix}\]钦定选与不选仍然通过调整点权实现。按套路维护即可。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
P8820 [CSP-S 2022] 数据传输
闲话：仍然记得当年走出考场时，le0n 跟我说这道题是动态 dp。然而当时的我并不知道这是什么。
静态 ddp 问题。仍然使用矩阵描述转移，没有修改意味着不需要树剖。
P9597 [JOI Open 2018] 猫或狗
树上连通性问题，考虑将连通性计入 dp 状态。设 \(f(i,0/1)\) 表示在 \(i\) 子树内使得 \(i\) 不与 \(1/2\) 连通的最小代价。可以得到转移方程：
\[f(i,0)=\left\{ \begin{aligned} &\sum_{j} \min\{f(j,0),f(j,1)+1\} && a_i \neq 1 \\ &\infty && a_i=1 \end{aligned} \right. \]\[f(i,1)=\left\{ \begin{aligned} &\sum_{j} \min\{f(j,1),f(j,0)+1\} && a_i \neq 2 \\ &\infty && a_i=2 \end{aligned} \right. \]点权带修，考虑动态 dp。
先树剖，记 \(i\) 的重儿子为 \(\text{son}_i\)，\(g(i,0/1)\) 表示不考虑重儿子的答案，改写转移方程。
\[f(i,0)=g(i,0)+\min\{f(\text{son}_i,0),f(\text{son}_i,1)+1\} \]\[f(i,1)=g(i,1)+\min\{f(\text{son}_i,0)+1,f(\text{son}_i,1)\} \]写成矩阵就是
\[\begin{bmatrix} g(i,0) & g(i,0)+1 \\ g(i,1) + 1 & g(i,1) \\ \end{bmatrix} \begin{bmatrix} f(\text{son}_i,0) \\ f(\text{son}_i,1) \end{bmatrix}= \begin{bmatrix} f(i,0)\\ f(i,1) \end{bmatrix}\]线段树维护即可。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。注意修改和查询的一些细节。
树上启发式合并
树上启发式合并用来处理树上某些离线问题。
- 更一般地，将重子树和轻子树分开处理。\(\mathcal{O}(n \log n)\)。
- 在数颜色等问题中，可以用
std::map记录答案，启发式合并。\(\mathcal{O}(n \log^2 n)\)。实现较简单。
CF600E Lomsat gelral
Sol 1*：一般的 dsu on tree 做法。先遍历轻子树，统计轻子树的答案，但是清空轻子树带来的贡献。再遍历重子树，统计重子树的答案，保留贡献用于继承。再遍历轻子树，将轻子树的贡献计入。
具体做法是开一个桶，记录每种颜色的出现次数。遍历轻子树时利用桶算答案，但是要把对桶的改变撤销掉。最后算重子树的答案，对桶的改变不清空。
时间复杂度 \(\mathcal{O}(n \log n)\)。
Sol 2：不妨更暴力一点。对树上每个点开一个 std::map 记录子树中每种颜色的出现次数。再用两个数组记录子树中出现次数最多的颜色的出现次数，以及答案。将儿子的 std::map 合并到父亲时，将小的信息合并到大的上。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
CF208E Blood Cousins
线段树合并 / dsu on tree 适合解决树上深度问题。
对询问离线，预处理倍增数组，将 \(u\) 的询问挂到 \(u\) 的 \(k\) 级祖先上。开一个桶统计深度，仍然是先遍历轻子树，清空桶，再遍历重子树。计算挂到 \(u\) 上的答案只需要统计桶里有多少个深度为 \(dep_u+k\) 的点即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF246E Blood Cousins Return
与上一题差不多。这里我们把桶换成 std::set，计算答案时只需要查 \(dep_u+k\) 的集合大小。
时间复杂度多了一个 set 的 \(\log\)。
CF1709E XOR Tree
考虑树上差分，令 \(d_u\) 表示根到 \(u\) 的异或和，那么一条链 \((u,v)\) 的异或和就是 \(d_u \oplus d_v \oplus a_{\operatorname{lca}(u,v)}\)。
从叶子向上逐步修改，由于可以改为任意数，那么自然可以通过二进制高位置为 \(1\) 的方法来把异或和强制改成不为 \(0\)。这说明我们可以通过仅改 \(u\) 实现让 \(u\) 子树合法。
考虑启发式合并，对每个点开一个 std::set 维护其子树内所有点的 \(d\) 信息。将儿子合并到父亲时，只需要查找是否存在 \(d_x \oplus d_y \oplus a_{u}=0\)，如果有就改一下 \(u\) 的值。
而改掉 \(u\) 会让 \(u\) 子树内全部合法，相当于“断掉”了 \(u\) 这棵子树，所以要将 set 清空。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
CF570D Tree Requests
将询问挂到对应节点上，把同一深度的信息压成一个二进制数，只维护奇偶性，那么能排成一个回文串的充要条件为 \(\operatorname{popcount}(x) \leq 1\)。
dsu on tree 可以轻松维护。无论加入还是删除都是把一个二进制位异或 \(1\)。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
P9886 [ICPC2018 Qingdao R] Kawa Exam
考虑断边的影响，会发现只有断掉割边才会使答案改变。可以先边双缩点，每个连通块都是一棵树。断掉树边 \((u,v)\) 会形成 \(v\) 子树内和子树外两块，只需要分别统计两块中的众数。
考虑 dsu on tree 处理，那么子树内众数就搞定了。对于子树外数颜色，可以初始时先把所有颜色的贡献加入进来，把撤销和加入反过来。这样撤销掉的都是 \(v\) 子树内的贡献，统计到的自然就是子树外的贡献。
实现细节不少。这里写两个比较重要的细节：
- 统计答案。因为还要加上其他连通块的答案，可以每次处理当前连通块之前预处理一个不断边的答案，将这个连通块内的答案都减去这个值，最后整体加上全局的答案。
- 快速维护众数。可以写一个计数器，用类似莫队的方法通过指针实现。
时间复杂度 \(\mathcal{O}(n \log n)\)。
虚树
参考 虚树 - OI Wiki。
虚树用来处理与树上关键点有关的问题。通过建虚树提取关键点和与其有关的信息，从而降低点数。
可以用单调栈建立虚树。对关键点按照 dfn 序排序，用单调栈维护 dfn 序递增的一条链。插入时通过判断与栈顶的 \(\text{lca}\) 的关系决策是否要改变链的结构，出栈时连边即可。
时间复杂度 \(\mathcal{O}(n+m \log n)\)。
P2495 [SDOI2011] 消耗战
考虑朴素的 dp。设 \(f(u)\) 表示断掉 \(u\) 与 \(u\) 子树中所有关键点的代价。枚举儿子 \(v\) 进行转移。
- 如果 \(v\) 是关键点，\(f(u)\leftarrow f(u)+w(u,v)\)。
- 如果 \(v\) 不是关键点，\(f(u)\leftarrow f(u)+\min\{f(v),w(u,v)\}\)。
时间复杂度 \(\mathcal{O}(nm)\)，不能接受。
注意到 \(\sum k_i=\mathcal{O}(n)\)，并且转移时只与关键点的信息有关。考虑建虚树，虚树上的边权设置为原树上两点路径的最小边权，把 dp 过程放到虚树上，转移不变。
这样一次转移的复杂度降为 \(\mathcal{O}(k_i)\)，总复杂度 \(\mathcal{O}(n+m\log n)\)。
P4103 [HEOI2014] 大工程
先建虚树，边权设置为原树上两点的距离。
对于第一问，考虑对每条边计算贡献，其被经过的次数就是这条边两端子树中特殊点的数量。对每棵子树统计子树中特殊点数量即可快速计算。
对于后两问，维护每个点到其子树中特殊点的最远/最近距离，转移平凡。
时间复杂度 \(\mathcal{O}(n+q\log n)\)。
CF613D Kingdom and its Cities
先把虚树建出来，考虑怎么统计答案。
先判无解，如果有两个关键点存在父子关系，则无论如何也断不开了，输出 \(-1\)。
对于非关键点 \(u\)，如果存在 \(\geq 2\) 棵子树中有没断掉的关键点，则必须删了 \(u\)。这么做会消除 \(u\) 子树中所有关键点对 \(u\) 祖先的影响。
对于关键点 \(u\)，我们不能直接删除 \(u\)，从而只能断掉每一棵存在关键点的子树。
一遍 DFS 就可以算出答案。\(\mathcal{O}(n + q\log n)\)。
P3233 [HNOI2014] 世界树
P4426 [HNOI/AHOI2018] 毒瘤
点分治 & 边分治
树分治适合处理大规模的树上路径信息问题。
点分治。将路径拆成经过根节点和不经过根节点的，不经过根节点则必然被某棵子树完全包含，递归下去分治处理，经过根节点的又可以进一步拆成以根为端点的路径拼起来。于是我们只需要处理每个点到根节点的路径信息。
P3806 【模板】点分治 1
点分治模板。
对询问离线，开一个桶记录子树中存在哪些到根节点的距离，只需要判断是否存在两条路径拼起来 \(=k\)。
注意撤销不能用 memset，要用队列记录下那些距离存在过，只撤销队列里的位置。这样复杂度才是对的。
时间复杂度 \(\mathcal{O}(mn\log n)\)。
P2634 [国家集训队] 聪聪可可
点分治板题。
对所有边权和统计的路径长度模 \(3\)，问题转化为长度为 \(0\) 的路径数量。开个桶记录一下就好了。
但是直接用 \(c_0^2+2c_1c_2\) 计入答案会算重，因为这样会在根把子树内的答案也算进去。那么我们减掉子树内的答案即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
P4178 Tree
点分治，用树状数组维护当前到根节点距离为 \(x\) 的路径数量。查询两条路径拼起来 \(\leq k\) 的数量查询就是在树状数组上查前缀和。撤销仍然需要维护队列。
时间复杂度 \(\mathcal{O}(n \log n \log k)\)。
P4149 [IOI2011] Race
点分治，用一个桶 \(mn(x)\) 记录到当前根节点距离为 \(x\) 的最小边数。查询就是两条路径拼一下。
时间复杂度 \(\mathcal{O}(n \log n)\)。