（7.17）早就想学点分治了……今天状态不太在线，眯一会写篇笔记来理理思路。

--------------------------------------------------------------------

　　（静态）点分治是一种利用无根树性质暴力分治的思想，可以在O(nlogn)的复杂度下统计可带权树上的路径信息。

　　像是这道例题，多组询问是否存在长度为k的路径，需要我们预处理出一个储存所有路径长度信息的桶。

　　点分治的做法，就是选定一个合适的根节点，把树上的所有路径分成不重不漏的两部分来统计：

　　1、经过根节点u的路径；

　　2、在u某个子树中的路径。

　　每次分治我们会统计出第一种路径的信息，然后递归进入u的每个子树，将第二种路径看作它的子树内的子问题来求解。

　　首先，我们要选定一个合适的根节点开始分治。最理想的根节点要满足它的每个子树大小都基本一样大；于是我们就想起了重心这个好东西。

　　　无根树的重心u的性质：

　　　　1、最大子树的大小最小。

　　　　2、最大的子树大小小于等于树大小的一半。

　　如果每次选定该子树的重心为根来进行分治，我们就可以保证递归的进行不超过logn层。

--------------------------------------------------------------------

　　接下来是分治和统计的过程。O(nlogn)实际上是算法框架的复杂度，实际复杂度会随统计手段而改变。

　　针对这道题来说，我们通过一次暴力dfs统计出当前子树中每个点的路径信息（包括根自身，深度为0），然后继续很暴力地两两组合路径，然后就出问题了……

　　直接合并任意两条路径是行不通的，因为这两条路径可能来自u的同一个子节点v。此时我们得到的这条不合法路径的信息把u--->v的这条边统计了两次，所以我们要再遍历一遍它的每个子树，把这些不合法路径去掉。具体的操作可以看代码，用到了容斥原理。

　　大概不管是谁看到这里都想吐槽了：这个常数大到哪里去了？每回都要多跑一遍O(n)的搜索和O(n^2)的统计，虽然复杂度没有变，但是接受不能。

　　实际上该题分治的过程有第二种写法，但是我还没有掌握，所以今天就先更新到这里。

--------------------------------------------------------------

（7.19）肝出了点分治的第二种写法。

　　我们完全可以通过直接进行不重不漏的统计来避免容斥。处理u时，我们每次跑出点u的一个子树内的所有深度，把它们计入子树深度信息的同时，与之前得到的别的子树的信息组合，统计答案。注意这里要把点u本身计入这个child数组中，深度为0，这样就涵盖了路径结尾在u的情况。

代码：

　　这段代码的实测效率比上一种写法快了一倍（开O2快10倍@w@）。下面放上完整的代码：

由于通过枚举每一条可行路径来n^2进行统计，这种写法有很大的局限性。例如【P4178】Tree 这道题，直接枚举统计会爆炸，需要排序和双指针扫描的技巧来成段统计可行路径。在大多数情况下还是需要使用容斥去重的方法进行点分治。