点分治和树剖有一个相同点，就是算法都是从暴力经过一小步优化而来，但就是这一小步，让算法复杂度有了质的飞跃。
下面来讲一下这个算法的原理。
概览
其实“点分治”也是一个名不副实的算法，看完下面的讲述你就会发现这个算法根“分治”几乎无关。
点分治是专门解决树上路径统计的一种算法（树剖则是解决对树上路径的判断的算法）。
点分治的思想很朴素，就是DFS一下 $\text{lca}$ 的节点编号 $x$，然后统计 $\text{lca}$ 值刚好为 $x$ 的、满足题目条件的路径的数量，并累加到答案。
但直接进行统计还是炸裂的，点分治则是对这种统计方式做了一步优化
解决题型
上面说了，「点分治是专门解决树上路径统计的一种算法」，但并不是所有的树上路径统计都可以用点分治解决。
其实看完下面的实现，你就能知道它解决什么类问题，不过这里还是说一下。
就是首先，这个条件是形如“总和比某个值低”、“总和是某个值的倍数”等“可累加”的条件。
其中“可累加”指的是，如果知道了 $A$ 部分的某个值，和 $B$ 部分的某个值，那么 $A$ 和 $B$ 部分合并后的部分是否合法也一定知道。
但其他的条件目前还没有太明确，得自己去总结。
算法实现
下面说一下点分治的实现。
大体思路
我们拿“路径长度（路径上的边的边权之和）刚好为 $k$”问题举例。
注：原题链接P3806
就是我们考虑，当DFS到某个点 $x$ 的时候，就如上所说，设 $x$ 为 $\text{lca}$ 值。
然后，我们按顺序遍历所有子节点 $to$。
由于只要两个点 $y$、$z$ 满足 $y$ 和 $z$ 分别在 $x$ 的两个不同儿子及其子树内，那么 $\text{lca}(y,z)=x$。
并且所有满足条件 $\text{lca}(y,z)=x$ 的对 $(y,z)$ 只有满足上述条件的对。
所以，我们可以通过（另一种）DFS（方式）求出 $to$ 到 ( 所有 $to$ 及其子树内的点 ) 之间的距离（加上 $x \to to$ 的边权）的集合 $T$。
并维护当前所有遍历过的儿子（不包含当前遍历的儿子）的 $T$ 集合的并集 $S$。
接下来，只用看是否存在：
- 一个在 $S$ 中出现过的元素 $x$。
- 一个在 $T$ 中出现过的元素 $y$。
满足 $x+y=k$（其中 $k$ 为询问的值）即可。
这一点可以用标记数组解决。
具体而言，我们维护一个标记数组，表示每个元素是否出现于 $S$ 内。
但现在唯一的问题就在于，$T$ 集合只能暴力求出，但如果真的暴力，复杂度是炸裂的（可以被一条链的数据卡掉）。
优化算法
我们考虑，不优化求出 $T$ 集合的暴力DFS算法，转而优化外层DFS（枚举 $\text{lca}$ 值用的）。
我们先对于每个 $to$，暴力做DFS，并更新答案。
然后再枚举每个 $to$，此时 $to$ 及其子树无论以谁为根，都不会影响答案，显然。
而由于我们对于每个点，都要遍历两遍子树，所以复杂度是和深度有关的，是一个 $O(2^\text{dep})$ 的复杂度。
所以，我们就尝试把深度降到 $\log n$ 级别即可。
一种思路就是每次只选择 $to$ 及其子树的重心作为根，因为重心有一个特点：
- 如果以重心为根去重构整棵树，那么根节点（重心）的每个儿子及其子树的大小，都不会超过整棵树的大小的一半。
所以深度一定不超过 $\log n$。
扩展算法
不过无论如何，点分治只是一个工具类算法，得配合其他算法出现。
比如，另外一道题P4178，就得把标记数组换成树状数组。
还比如一些题，得在更新答案的时候用双指针，甚至还要配合优先队列等STL。
复杂度证明
其实这个证明非常好想。
上面其实已经说了一点了，就是复杂度是 $O(2^\text{dep})$ 的，而每次选择重心就可以让这个复杂度达到 $O(n)$。
对于其他的用点分治的题目的复杂度证明，可以采用以下思路：
- 看每个点对复杂度有多少贡献。
那个复杂度 $O(2^\text{dep})$ 就是这样求出的。