点分治算法分析
点分治用来处理有关数上路径问题。
所有路径对答案的贡献其实可以分成，所有过一点的路径+所有不过这点的路径。
不过这点的路径怎么算？可以以这点为根到它的子树里分治解决。
所以现在问题只有：1、所有过这点的路径怎么解决？2、复杂度怎么保证？
问题二：可以每次分治时以重心为根。这样最多分治\(logn\)次
重心：满足以此为根，所有儿子子树大小的最大值最小的节点。重心有一个性质：以重心为根的树，所有重心的儿子子树的大小一定小于\(\frac{n}{2}\)。这个性质的证明跟某一经典的贪心证明很像（好像是把数轴上的所有物品移到哪个物品上的花费最小）。
这个性质保证了最多分\(logn\)层。
问题一：方法不是重点，点分治重点在于分治，把求书上路径问题转化成求树上过一个点路径的问题，而且代价只是复杂度多了一个\(log\)。
注意的点
计数问题中一个一个去记答案是很蠢的，除非答案的数量级很小。
除了计数问题之外，还有所有关于通过根节点路径的最优化问题（选哪个为根），通常这类问题有单调性，可以判断答案在某个子树里。然后普通方法复杂度不对，用点分治最多\(logn\)层子树的性质优化算法。