点分树学习笔记

关于点分树的一些理解

定义与性质

点分树，就是把点分治中的每一次的重心连起来，构成一棵树。
由于重心的性质，点分治最多有 $\lg n$ 层, 所以点分树的树高最多是 $\lg n$

维护

一般维护两个值 $s1$ 和 $s2$ ，$s1$ 表示这个点的子树对于这个点的贡献， $s2$ 表示这个点的子树对于这个点的父亲的贡献。$s2$ 用于对 $s1$ 进行容斥

每次修改时要在点分树上不断跳父亲，修改点分树上父亲的信息。

每次查询时要在点分树上不断跳父亲，询问点分树上父亲的信息，一般要用到容斥。用 $s2$ 容斥 $s1$

具体看了题就理解了。

用途

一般用于静态条件下点分治可解，但是强制在线或带修的题。

维护树上点和点之间的关系， 树上的全局信息。

减少递归层数或限制一个点为根，计算过这个点的点对信息。

注意事项

点分树上的位置关系，距离关系，父子关系，祖孙关系，和原树上不同。

luogu6329震波

标签

点分治， 树状数组

思路

先考虑不带修的情况，那这就是道点分治裸题，但是这道题要求支持修改且强制在线。那么点分治就不能用了。

所以我们要用点分树。

对于每一个节点维护两棵树状数组 ($vector$ 存) , $s1$ 维护距离当前点距离为 $k$ 的点的价值和, $s2$ 维护距离当前点的点分树上的父亲距离为 $k$ 的点的价值和。

对于修改操作，改成增加，然后在点分树上不断跳父亲，修改 $s1$ 和 $s2$ 。

对于查询操作，在点分树上不断跳父亲，设询问点和父亲的距离为 $d$ , 那么对于每一层，把答案加上 $s1[fa].query(k - d) - s2[u].query(k - d)$ 用于去重，因为当前子树已经被计算过了。

维护两棵树状数组多麻烦啊，直接 $s1[fa].query(k - d) - s1[u].query(k - d - dis(u, fa))$ 或者 $s1[fa].query(k - d) - s1[u].query(k - dis(u, x))$ 多方便，然而要注意 点分树上的位置关系，距离关系，父子关系，祖孙关系，和原树上不同。 所以这样做是错误的。

Code

[ZJOI2007]捉迷藏

标签

点分治，堆

思路

这道题实际上是要求动态维护树的直径。

$LCT$大法好 ，考虑点分树解决。

像静态树直径一样，需要对于每个点维护从这个点伸入子树的最长链，和伸入不同子树的最长链和次长链，支持插入和删除，可以用可删堆实现。

对于每个点维护两个堆， $s1$ 维护从这个点的子树伸向这个点的链， $s2$ 维护从这个点的子树伸向这个点的点分树上的父亲的链。把这个点子节点的 $s2$ 的堆顶插入到一个堆，这个堆就是这个点的 $s1$ .

维护一个 $ans$ 表示答案的堆，把 $s1$ 的堆顶和次堆顶加起来，插入一个堆，这个堆就是 $ans$ , 因为是动态的，支持删除, 所以要用堆维护。

关于修改，没什么好说的，直接维护就好, 删除原来的答案，加入改变后的答案.

Code

[ZJOI2015]幻想乡战略游戏

标签

点分治

思路

一句话题面： 动态维护树的带权重心。

对于每一次修改，求一遍重心，复杂度显然是 $O(n^2)$ 。 发现这道题保证每个点的度数不超过 $20$ 所以只要限制层数，那么就可以优化复杂度。考虑用点分治，使层数为 $O(\lg n)$ 。

定义一个点的带权距离和表示树上所有点，到这个点的带权距离之和

根据重心的一些性质， 对于一个点，从它到重心，每个点的带权距离和一定是单调的。

所以从点分树的根开始，枚举它在原树中的每个子节点，考虑能不能更优，如果更优，递归到这个子节点所在联通块的重心。直到找不到更优解为止.

那么需要考虑如何判断是否更优，即如何查询一个点的带权距离和。 对于每个点，在点分树上维护三个值 $s1$ , $s2$, $s$

$s1$ : 这个点的子树中的点到它的带权距离和。

$s2$ : 这个点的子树中的点到它点分树上的父亲的带权距离和。

$s$ : 这个点的子树的带权大小

修改很套路，查询暴力跳 $fa$ ， 一个点父亲对带权距离和的贡献就是 $(s1[fa] - s2[u]) + (s[fa] - s[u]) \times dis(fa, x)$

Code