一句话

点分治

对于一棵子树，即正常 dfs 的根改成该子树重心，递归下去是按原树儿子所在子树的重心（每次找一遍），变成了子问题，可以处理与树形态没什么关联的问题

发现 siz 每次减半，故深度 log 层；同时 siz 大小总和的复杂度是对的

由于总是处理的整棵子树，而答案与子树遍历关系无关，所以一定是对的！！！同时遍历处理什么信息的复杂度也是对的（花了一晚上理解，真的确确实实是对的）

附一张图：

边分治

把点分治中的点换成边，这条边的两边子树大小相平衡，也就是当前子树找的不是点（重心）而是一条边了，继续往下找也是找的边；但是注意它在菊花图上就不适用，所以要把这棵树变成二叉树来获得好的性质.

点分树

其实点分树的题就是把点分治的题从一个点到几个点，多次询问，有修改

把点分治中每次找的重心先一遍存下来，避免之后每次都要找重心；他有很好的性质：

• 深度 \(\log\) 层；
• \(u,v\) 的 \(lca\) 在原树中是 \(u,v\) 路径上的一个点，可以用来 \(dis(u,v)=dis(u,lca)+dis(lca,v)\)（\(dis\) 指原树中的距离）

这样，我们想一个暴力，然后把它放到点分树上去就可以了

虚树

只有选定点和它们 \(lca\) 的树，若选定 \(m\) 个点，则加上 \(lca\) 一共 \(2m-1\) 个点，两种构建方式：

• 按 dfn 排序后两两加入相邻两个点的 lca，去重
• 随便什么顺序加，但是用个栈维护最右链，注意若栈弹完了要加入栈中最后一个点与当前点的 lca

最常用最好写的还是第一种，不过第二种是线性的，闲得可以用，其实第二种也比较好写

用法：如果两点之间跳很多中转点是没用的，那可以用虚树来避免很多的中转点，同时也适合 dp 什么的

动态 dp

用数据结构维护可合并的动态规划，有两种方式：

• 形如线段树维护区间背包
• 维护矩阵，可以改变矩乘运算：\((+,\times),(\land,+)\)（即 \((\min,+)\)）什么的

归并树

把归并排序过程中的每个序列记下来了，注意空间复杂度 \(O(n\log n)\)，由于每个节点变成了一个序列，可以干很多事情（例如每个序列上走指针什么的）

替罪羊树

暴力的平衡树，采用重构方法：

• 设不平衡率 \(\alpha\)，左右子树大小比值小于这个值就重构该子树
• 每隔一段固定时间重构整棵树

虽然暴力，但是由于不旋转可以做比普通平衡树更多的一些事情，同时可以作为数据结构的外层嵌套.