其实感觉本文应该放在分治里面讲……算法学习笔记(31): 分治
在经典的序列分治中，我们是对于每一个点，求出经过这个点的那些区间的贡献。
在点分治中，同样我们是对于每一个点，求出经过这个点的那些路径的贡献。
放在边分治中，则是求出经过某条边的那些路径的贡献。
点分治
在一般序列分治中，我们是找中点，在点分治中，我们如何减少问题规模？
观察各心性质，发现重心的性质优良，满足其所有子树的大小不超过 \(\lfloor \frac n 2 \rfloor\)。
于是如果我们按照重心划分，那么每一次，问题规模至少减半，那么剩下的问题就是如何合并所有子树的贡献？
可以一个一个子树的贡献，然后加入，就像扫描线一样。
但是注意到子树间不可以相互贡献，也就意味着必须先求出子树对前面加入子树的贡献，在将这颗子树的贡献加上。
在处理完经过这个点的路径之后，我们就可以大胆的删除这个点了！（标记被删除，而不是真的删掉……
然后我们就得到了规模减少了很多的一堆小问题了，递归处理即可。
这是板子题，拿来练手。
这里对于信息的加入和处理，考虑到 \(k \le 10^6\)，可以开一个桶记录。
注意不要每次将这个桶清空，而是记录修改的位置，一一还原，因为两者的数量级差距太大……
接下来是一些写点分治的注意事项：
- 在求重心的时候，有两种做法，一种是基于错误，但是正确的做法，可以参考 ## 一种基于错误的寻找重心方法的点分治的复杂度分析 一种是最常规的做法，这里说后者。
- 注意求重心时我们需要求 \(\max(siz_y, n - siz_x)\)，此时 \(n\) 需要更新为当前连通块的大小，这在分治进入这个分支的时候进行更新。
- 注意进入分治的根是找到的重心，而不是当前重心的某个儿子（虽然这样也可以骗过很多分……
代码就放这里了：云剪切板 - 洛谷
边分治
边分治看来才是最像序列分治的东西。
边分治找一条将两边均分的边是最优的，这和序列分治类似，但是很可能存在一个菊花图，使得不存在两边均分的情况，所以在边分治之前，我们需要对于这张图进行变化：三度化。
也就是说，如果我们使得每一个点的度数 \(\le 3\)，那么我们就可以尽可能的均分这颗树了。
那么具体的操作大概就是把树变成如图：
也就是新建一点点点和边，使之三度化即可。这样空间都还是 \(O(n + m)\) 的，但是常数略大，点数是原本的两倍，边数则接近 \(4\) 倍，所以不是那么的优秀。
值得注意的是，新建的这点点点和边必须不影响答案！
边分治的优势在于我们每次只会产生两个子树，我们只需要对于一棵子树进行处理，在另一颗子树中进行贡献查询即可，也就是说我们只需要构建一次某一边的静态结构。
但是根据 CMD 的说法：
事实上,点分治如每次合并(直接重建)两个最小的静态结构,并且处理之间的询问,复杂度仍然是正确的。边分治在比较经典的题目中没有多大优势。
我不太清楚这是如何做到的。
接下来是一些注意事项：
- 由于此时我们需要删边，所以用
vector存图就那么的毒瘤了，所以使用链式前向星存图，从 \(2\) 开始，双向边是相邻的，且异或为 \(1\)，所以可以快速的找反边来删了。不嫌麻烦可以用set删
- 还是进入分治的子树大小要特别注意，不然样例过了，却发现
TLE的很惨……
参考代码在剪切板末尾：云剪切板 - 洛谷
点分树，边分树
咕，暂时不太会。
参考文章：