概述
-
树分治通过树的唯一连通性质，递归地求解树上路径（主要是路径长度）相关的问题。
-
树分治主要包括点分治和边分治，但到目前为止我都不知道边分治有什么用。
点分治
-
点分治通过选取点作为分割来求解树上路径问题。
-
较具体地说，如果我们选定一个关键点 \(key\) 来分割当前处理的（子）树，那么路径可以分为以下三种：
-
1.端点为 \(key\) 的。
-
2.过 \(key\) 的。
-
3.某个子树内部的。
-
-
从而我们可以处理前两者，递归求解第三者。
-
我们以求解“树上长度不大于 \(k\) 的路径有几条”为例。注意，\(k\) 可以多组询问，但那代表着带上对应的常数，又或者 FFT，反正我不会。
当前路径的处理
-
定义 \(is_i\) 表示已经考虑完的子树中到 \(now\) 截止的路径中，长度恰好为 \(i\) 的路径的数量。定义 \(ta\) 为其树状数组。
-
对每个子树，规定子树的根的 \(dis\) 为当前节点与其的边的长度。
-
从而可以 dfs 求解整个子树到当前节点的距离。则每到一个点 \(i\) 就有 \(ans=ans+ta(k-dis_i)\)。
-
注意，不可以任意对位乘地求解所有长度的路径条数，复杂度是假的（每个子树都带一个当前子树大小 \(\times\) 已处理子树大小和的常数）。
-
将 \(dis\) 丢到一个栈里。栈记录的是到当前节点的可行距离。
-
回到当前节点后，用 \(dis\) 来更新 \(is\) 也即 \(ta\)。
关键点的选择
-
树的所有点都是割点。然而，分治的基本要求一般为“子问题尽量小”。或者，至少，子问题尽量平均。
-
这里可以参考主定理（对于每个 \(key\) 来说，它的 \(f=siz_{key}\)，最坏情况下 \(a=b=2\)）。
-
所以要设法求出对应子树的一个点，使得其各个子树大小相对平均。
-
具体来讲，先暴力 dfs 一遍求一下每个点的最大子树（注意也包括向父亲方向的那一棵，这就要求一个 \(num\) 来记录当前处理的子树的整体大小），然后如果 \(mxsub_{rt}>mxsub_{now},rt=now\)。
-
注意，没完。下一层的递归的 \(num\)，必须由本层的 \(siz\) 而来，但是第一遍 dfs 得到的 \(siz\)，不是以 \(rt\) 为根的情况。所以必须再来一遍，把 \(siz\) 处理好。
-
然后进一步递归即可。
-
我知道写的很烂，轻喷。而且就是没有标程，得去看 P3806/4178。主要是...啧。这个东西，随着处理的问题不同，维护的东西也不太一样，当然总归是求树上路径。再有就是，我还没太想清楚写法，目前的可以说是凭感觉写的。
P4178 Tree
- 题意略。只是把 \(=k\) 改成了 \(\leqslant k\)，于是只要维护一下前缀和就好了，其他没有什么区别。
CF150E Freezing with Style
-
题意：给出一棵带边权树，求一条路径，其边数 \(\in [L,R]\) 且边权中位数最大。特别地，这里中位数在偶数个时取中间较大的。输出任意最优路径的两个端点。
-
数据范围：\(n\leqslant 10^5,7s\)。
-
首先显然把边权离散化，然后考虑中位数的一个套路：二分答案，转化为 \(01\) 判定问题。鉴于这里我们难以预先知道路径长度，不妨令 \(<mid\) 的为 \(-1\)，\(\geqslant mid\) 的为 \(1\)，于是和 \(\geqslant 0\) 就说明是合法解。
-
树上路径问题，考虑用点分治...记录到根的，有 \(k\) 条边的所有路径中的最大权值（当然是 \(01\) 转化后的啦），于是合并的时候只要查询...记当前路径长度为 \(ln\)，权值为 \(vn\)，查询 \([\max_{i=L-ln}^{R-ln} mx+vn\geqslant 0]\) 即可。
-
我们看到随着二分的 \(mid\) 变化，需要多次点分治。考虑使用点分树...诶诶诶？好像点分树在这里完全没有作用啊？边权都变了？
-
那就暴力重新分治，这首先是 \(O(n\log^2)\) 的...然而区间查询最大值...线段树维护的话，\(O(n\log^3)\)。纸面 \(4.9\times 10^5\)...乍一看是不卡的，但线段树和点分治都是大常数 qaq。
-
所以...这位先生，能否占用你一点时间，我想向你介绍一下我们伟大的神器——单调队列按秩合并！
-
桥豆麻袋！不是，我该从什么地方开始吐槽？单调队列？合并？按秩合并？
-
别急。首先我们考虑这个问题是否满足优先队列的形式：似乎是可以的。
-
如果我们将当前子树的结果排序（事实上，改用 bfs 实现就足以达到这个效果），那么随着枚举当前子树的结果，\(L-ln\) 和 \(R-ln\) 都是单调不降的。
-
故只要在扫的时候，不断地移动重心这边结果数组上的 \(hd,tl\)，使得 \(hd\geqslant L-ln,tl\to R-ln\) 即可，这里 \(\to\) 表示尽量趋近，即不超过的前提下最靠近。
-
不妨记 \(num\) 为当前分治的子树点数。这里重心这边的结果数组显然不能是 \(1\sim num\) 的一个密铺，而应该本身就是一个单调队列；特别的是，这个单调队列的尾端竞争是有限的——不能因为尾端竞争使得一个可能的，完整的转移来源区间中一个数都没有。
-
然后考虑怎么合并：暴力合并单调队列就是从两者的队头不断取元素，尾端插入到一个新的单调队列中，显然是 \(O(siz+siz)\) 的；但我们可以将较小的单调队列中的元素插入到较大的单调队列中的对应位置，照样进行尾端竞争操作。
-
乍一看每次都要找位置是 \(O(\min(siz)\log max(siz))\)，实则不然，发现插入的位置也是单调递增的，故只要双指针...单指针？即可。
-
分析一下合并复杂度：乍一看是类似重剖的启发式合并，还是带 \(\log\)，然而仔细一想...仔细一想这是 \(O(siz+siz)\) 啊摔！双指针会扫完的啊，拜托...
-
看来这条路走不通——事实上转移求值部分似乎也是 \(O(siz+siz)\)，这还不如线段树呢，毕竟我们知道这个的本质是 \(O(n^2)\) 的树上背包...不对，背包是乘，这个是加，设有 \(k\) 个儿子，第 \(i\) 个转移上来的儿子会被后面影响 \(k-i\) 次。
-
嗯？这好像暗示我们把小儿子——我是指深度较小的儿子——放到前面去。嘛，毕竟复杂度要么是优化下来，要么是分析下来，我们分析一手试试：
-
若总有 \(siz\leqslant sizn\)...哦这是长剖。可以认为是合并上来的儿子带了 \(2\) 倍常数，于是忽略合并复杂度。芜湖！消了一只 \(\log\)！只要在第一次点分治的时候将各方向儿子排序就好啦，这一排序也是 \(O(n\log^2)\)！
-
注意到这样一来维护那个密铺就可以，没必要将其简化到一个单调队列。实现也容易了不少呢。另外最好还是建出点分树，我是指不要每次都重新找重心，以减小常数——这是古早 CF 题，在更新服务器后...强制运行时间翻倍。
点分树
- 即可持久化点分治，将点分治的树形结构（重心之间的父子关系）拉下来，于是树高为 \(O(\log)\)，这相当于随机数据的树高可以跑很多暴力。
P6329 【模板】点分树 | 震波
-
题意略。
-
考虑容斥，即在每个重心处用树状数组存每个距离的点的价值和，又另外存在父重心看来我这棵子树的每个距离的点数，然后从节点向根暴力回跳容斥即可。
-
修改也容易，思路基本一样，略。