点分治、边分治

点分治

淀粉质

常见题目套路：求出具有某一条件的路径个数/求出一条最优的路径

核心思路是：每次选取一个点 $u$ ，统计所有经过这个点的路径，然后把这个点删去，对于剩下的森林执行同样的操作。

如何统计？所有经过点 $u$ 的路径分成 3 部分，$v_1 - u - v_2$，其中 $v_1,v_2$ 不在同一个子树之中，然后每个点存储需要的信息，最后合并。
统计完点 $u$ 后，把它从整颗树里面删去，以后不需要用到它了。

如果每次选取的点都是子树的重心，那么复杂度就能够达到 $O(n \log n)$。

总结一下，就是如下流程：
对于一颗树 $T$：

1. 找到重心作为根。
2. 对每个子树，依次进行如下 3 步操作：
   i) dfs 求出每个子树的到当前根的信息；
   ii) 对于子树的所有节点，与前面的子树的信息进行合并求解答案；
   iii) 将这个子树节点的所有信息合并。
3. 删去根。
4. 对于根的每一个子树，回到第 $1$ 步，直到只剩下一个节点。

信息究竟是什么意思呢？
举个例子，求树的直径。（这是上文说的求出一条最优的路径类型题目）
每个节点储存的信息就是到根的距离 $dis$，问题就是求出 $\displaystyle\max_{v_1,v_2 \text{不在同一子树}} \left(dis_{v_1} + dis_{v_2}\right)$。
只需要维护之前所有子树中 $dis$ 的最大值 $mx$ 即可，然后对于当前子树的所有 $dis$ 与 $mx$ 相加即可求出最大值。