点分治总结(未完成)

点分治常用于静态树上的路经统计问题，我们可以很自然的设计出这样一种分治算法：
1.找出根结点Root；
2.计算以Root为根的树的答案；
3.删除结点Root，分治解决Root的每个子树；
但这样并不是最优，当树退化成链时，递归层数就会退化为O(N), 整个程序时间复杂度也会退化成O(N ^ 2)。
为了解决这个问题，我们每次找的Root必须是树的重心。这样的话递归的复杂度就能稳定在O(N)。

树的重心：

树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。 --百度百科

根据树的重心的概念，

点分治总结(未完成)

原文：https://www.cnblogs.com/mcggvc/p/12304733.html