【题解/学习笔记】点分树

点分树 | 震波

\(\text{Solution:}\)

是点分树的模板，这里讲一讲点分树。

本质就是把点分治的每一层分治重心给记录下来了，自然就形成了一棵树，并且树高是 \(O(\log n)\) 的。这很显然。

那么，考虑点分治的过程，实际上就是从点分树从根往下计算答案的过程了。

如果我们要计算点 \(x\) 的答案，对应地，应该是从根分治到点 \(x,\) 逆过来，就是从 \(x\) 跳到点分树的根。

所以，我们对答案维护只需要从这个点往上跳就好了。

那么我们考虑这个过程中哪些点对答案有贡献：

显然是跳到的点子树内距离根为 \(y-dis(x,now)\) 的点。因它们可以拼成一条长 \(y\) 的路径。

所以我们只需要对每个子树维护这个东西即可。一个是维护自己子树内部对它自己的贡献，另一个需要维护自己子树内单点对其父亲的贡献。

于是，应用容斥原理，计算其父亲子树内除 \(x\) 子树外其他点对它的贡献就是用总贡献减去 \(x\) 子树内对其父亲贡献为 \(y-dis\) 的部分。

而我们每次询问的是一个前缀和，所以可以树状数组维护。

由于点分树结构优秀，所以暴力跳的复杂度就是对的了。

同时，注意到点分树上的结构和原树的还是差别很大，所以我们需要在原树上面获得两点距离一类信息，而计算距离需要找 \(LCA,\) 利用欧拉序 \(st\) 表的科技就可以做到 \(O(n\log n)\) 预处理， \(O(1)\) 询问即可。

总之，点分树有以下特点：

对应每个节点是点分治的分治重心

树的结构非常均匀，树高是 \(O(\log n)\)

树的结构与原树关系很小，很多信息需要在原树里面获得

需要注意原树和点分树的差异，从而思考清楚两部分的信息处理

然后考虑答案所求在点分树上如何统计，从而确定如何统计信息，需要维护哪些信息

进而思考如何维护信息

大概就是这样的流程。至于修改操作：之所以建立点分树就是因为修改使得每次需要重复找重心进行计算，但这些修改对树结构没有影响，所以这些操作完全是不必要的，所以在点分树上修改就可以做到一个 \(\log n\) 复杂度

所以这些维护信息的数据结构往往还需要支持修改

如这题，就可以用树状数组来维护修改维护前缀和了。

至此，点分树介绍以及本题题解完全结束。

代码中附注释。