点分治和点分树的相关概念

点分治： 点分治是一种树上分治的算法。核心思路就是对于每个点上的问题，将所有问题分成两大类，一大类是该点连接的每个子树内部的问题，这一类问题可以递归处理每棵子树；一大类是这些子树之间的问题，这一类问题可以归并处理。

边分治： 边分治也是一种树上分治的算法。核心思路就是对于每条边上的问题，将所有问题分成两大类，一大类是该边连接的两棵子树内部的问题，这一类问题可以递归处理；一大类是连接的两棵子树之间的问题，这一类问题可以归并处理。

对于所有树上分治问题，一般用点分治居多，因为边分治算法在处理菊花图时的时间复杂度会降掉 $O(n)$，并不能保证永远是 $O(n\log n)$ 的效率。而点分治则可以保证永远是 $O(n\log n)$ 的时间复杂度。

点分治的时间复杂度证明

点分治是按照每个点的子树依次递归下去的。对于一棵树，我们可以保证将它的重心删去之后剩余所有子树的最大节点数一定不超过 $\frac{n}{2}$。

我们这里可以用反证法，假设对于树的某一个重心 $u$，删掉之后存在某一棵以 $v$ 为根的子树的节点数 $k > \frac{n}{2}$。此时我们尝试将 $v$ 变成重心，那么将 $v$ 删去，则 $u$ 所在的子树的大小就应该是 $n-k$，由于 $k > \frac{n}{2}$，所以 $n-k < \frac{n}{2} < k$，而 $v$ 的另一边的每棵子树的节点数也一定不超过 $k-1$，那么此时 $v$ 作为重心每个子树的大小都 $<k$，显然这就与 $u$ 是重心矛盾了。由此得证，我们把重心删完之后剩余所有子树的大小都 $\leq \frac{n}{2}$。

而由于点分治是每次往子树递归处理，因此点分治的时间复杂度应该和它递归的层数有关，上面我们证明了如果将重心作为根节点，则每个子树的大小都 $\leq \frac{n}{2}$，因此我们只要每次选择当前子树的重心往下递归，则每次往下一层节点数都会至少减半，这样递归的层数最多只有 $\log n$ 层。所以时间复杂度为 $O(\log n)$

点分治的思想

通过上述时间复杂度的证明，我们也能基本得出点分治的核心思想。

最开始从整个树开始做，对于整棵树求一下重心是什么，然后将问题转化成若干个子问题和一个归并的问题，然后我们递归解决若干个子问题，然后再解决合并的问题，就能将整个问题解决。这就是点分治的核心思想。

点分树： 点分树其实就是动态点分治，由于过程中会建立一棵树，所以又叫点分树。点分树是用来存储点分治中选择重心的一个过程。对于点分树中的每一棵子树，他的根节点并不是原树中对应的根节点，而是这颗子树的重心。因此点分树的结构和原树是完全不同的。

点分树常用于多次查询的点分治问题，对于每个询问都需要用点分治来做，此时这若干个询问的点分治选重心的过程都是完全一样的，因此我们可以直接通过预处理的方式将选重心的过程存下来，对于每个询问都能直接复用。点分树的构建其实就是按照点分治的过程递归的建树即可。

如果对于每个询问我们都能用一个高效的算法，每一层都能快速的求，这样的问题就能用点分树来做。点分树中需要根据不同问题的需要存储一些相关的信息。