1. 定义
在点分治的基础上加以变化，构造一颗支持快速修改的重构树，称之为点分树
2.算法
2.1. 思路
点分治的核心在于通过树的重心来划分联通块，减少合并层数，从而降低时间复杂度
所以，我们可以按分治递归的顺序提出一颗树，易知树高至多为logn
具体的说，对于每一个找到的重心，将上一次分治时的重心设为其父亲，就可以得到一颗logn层的虚树（重构树）
举个例子，原树为：
新树为：
此时，有一个性质，所有子树的子树大小之和为nlogn
证明：每个点会被从根到它的路径上最多logn个祖先所统计，所以必然小于nlogn
所以在新树上修改，只需要暴力儿子跳父亲即可
2.2. 应用
统计一个点到其他点的点权和，即\(\sum_{y=1}^n dis(x,y)\)，对于任意一个y，找到它与x在虚树上的lca，易知在以此点为重心划分子连通块时x,y会首次被分割开来，因此该点必定在原树的x,y路径上。
所以我们只需要在这些lca的虚子树中寻找y即可，此时记录虚子树信息的作用便显现出来了。
而对于一个x，可能的lca最多存在logn个，因此通常使用暴力枚举+简单容斥的方法来统计y的贡献。
3.具体实现
3.1. 例题：P6329 【模板】点分树 | 震波
oj:https://gxyzoj.com/d/gxyznoi/p/P17
题意：维护一颗带点权树，需要支持两种操作：修改x的点权，查询与点x距离不超过k的点权值之和。
3.2. 思路
3.2.1. 建树
在找到第一个重心rt后，先遍历得到整颗树的信息，然后删除rt，再递归处理其他联通块
操作和点分治基本相同，但是将统计答案变为统计子树信息