点分治——树上路径统计

点分治有什么好处？我们为什么不直接用树形dp？

它多用了一个logn的代价，使得我们每次面对的都是过重心rt的路径。

这样，我们可以灵活用子树来处理。

而树形dp必须一次考虑所有过x的所有路径。必须还要多处理一个“和x有关”的信息，多了O(n)的时空。

点分治由于同一层不用考虑其他路径，所以复杂度和思维含量大大降低。

（分治都是这样干的。。）

然后需要修改。

动态点分治出现。

基本处理思想是，先点分治一遍找到分治树结构。

每个分治树上的点维护一些信息。

一般包括：自己管辖区域路径过自己的信息（这个是为了统计答案需要），和自己管辖区域对分治树father的影响（这个是为了更新迅速、拆解方便、不重复统计等。因为自底向上更新，只有一个father。不用枚举保存father的子树）

（子树的并不用维护，因为每次修改查询自底向上会处理到）

（我）经常还用的数组是：dis[x][d]，x到深度为d的father的距离。以及dep[x]x分治树的深度。

修改一般都自底向上修改。复杂度基于分治树高度的logn

查询差不多。

关键是处理好信息的维护。

分治的关键是：

1.可以有针对性地处理当前贡献。都是过mid的点对等等。

2.情况独立于其他的分治树节点。即划分子问题思想。这也为动态分治的方便维护打下坚实基础。

3.层数的logn加上情况独立，使得总复杂度是O(nlogn)，本质上的节省统计次数，在于当前层的合并有针对性，

可以左右许多东西，利用乘法原理，乘法分配律，交换律，一起统计。