点分治【产品说明书】
产品用途
本章讲述本产品的用途，即大规模处理树上路径。
例：给出一棵n个点的树，求树上有多少条长度为k的路径？
何谓大规模？事实上，当\(n\)的大小达到\(10^4\)，就已经不小了。
本产品可以解决的问题范围大约为\(n\leq 10^6\)
（注：笔者是口胡的）
\(\mathbf{Q.}\)本产品vs朴素算法
\(\mathbf{A.}\)Of Course本产品！
本产品
拥有美丽的时间复杂度（\(O(n\log^2n)\)，部分可桶排优化至\(O(\log n)\)）
朴素算法1
枚举不同的点对，dfs求距离，拥有可爱的时间复杂度\(O(n^3)\)
朴素算法2
枚举不同的点对，lca求距离，拥有可爱的时间复杂度\(O(n^2\log n)\)
朴素算法3
呃，不太清楚，但听说暴力能拥有可爱的时间复杂度\(O(n^2)\)
使用方法
本章讲述本产品的作用原理和实现方法。
原理简介
顾名思义，淀粉质点分治就是按照树上的节点进行分治。得益于树美丽的结构，我们可以轻松地分而治之。
一棵树，可以在一次分治下被切割如下几个部分：根节点，子树，子树，……，子树。
当然，也可能没有子树，或者子树是一个节点……
这些对分治没什么影响的小小问题，甚至称不上特殊情况呢
实现方法
分治点
那么每次分治的“根节点”应当如何选择呢？
可以画个图，但是笔者太懒，于是就口头解释
可以先暴力地考虑随便选一个点，然后思考可能存在的bug。
举一个极端情况：树是一条链。
由于随便选一个点，如果每次都选到链首作为根节点，那么总共需要分治\(n\)次。
（大寄的时间复杂度，甚至不如直接暴力）
所以随便选点肯定是哒咩的，选点的方法应该要符合某种规律。
这时候就该想想“树的杂七杂八东西”
树的杂七杂八东西，指：直径，中心，重心
发现重心是个好东西。
其实分治次数，与最大子树大小关联很强。
（主要是没自己证明，所以说法比较模糊，总之是这样的）
重心恰巧是这方面的专业户，它的最大子树大小不会超过\(n/2\)。（可以利用反证法轻松得证）于是我们把 当前要分治的这棵树的重心 作为根节点进行分治，这样就可以保证复杂度不爆炸了。
（关于怎么求重心，考虑到篇幅还是不提了awa）