点分治的基本思想
首先不考虑时间复杂度的问题，要不重不漏地统计树上路径问题，可以考虑一个简单的分类：对于一个点（后文的分治中心），将答案分为两类，通过该点的路径和不通过该点的路径。
首先在该点使用 Calc() 函数（当然不一定叫这个名字，本文就写作 Calc 了）计算第一类贡献（具体怎么计算后文讲），然后向所有没有计算过的相邻点 dfs，以他们为中心计算答案。
记住，在统计答案的时候要删去已经作为过中心的点（例如 $1 - 3 - 2$，那么先以 $3$ 为关键节点计算后，计算以 $1$ 为关键节点的答案，然而这个答案不存在，因为不能经过 $3$ 了），这是为了不重复计算，不然会使已经类答案重复统计
于是我们可以写出一个"点暴力"的不是很伪的伪代码:
void dfs(int u){
solved[u] = true;//不重复统计
ans += Calc(u);//当然不一定是累加的形式
for(auto v : edge_u){
if(!solved[v]){
dfs(v);
}
}
}它的复杂度是多少？Calc 本身的实现一般是比较暴力的，复杂度一般为 $O(size)$ 与子问题规模相关（子问题规模的大小就是删除已统计的点之后，要解决的点所在的连通块的大小）
这种"点暴力"显然是不优的，复杂度接近 $O(n^2)$，我们考虑优化。
点分治的复杂度优化
首先我们要了解树的重心的一个性质：
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
所以如果我们每次都把重心作为分治中心（也就是上文的关键节点，中心），显然每一层递归下去问题规模每次会减半，所以说复杂度优化至 $O(nlogn)$ （这个证明不是很严谨？感性理解）
所以我们要找到重心，首先进行一遍 dfs 求出 $size$ 和 $mss$ （最大子树大小），记住 $mss$ 要包括节点“头上”的子树。
这里有两个需要注意的地方。首先这个 $size$ 是相对于这个子问题而言的，也就是说我们是不会 dfs 到之前的分治中心上的。另外求头上的子树大小需要使用到当前子问题规模的总大小，然后减去该子树大小。值得一提的是，子问题的总规模就是从上一层的分治中心的视角来看的，该子树的大小（这个子问题是上一个分治中心的一颗子树），为了保证此时的 $size$ 数组是以上一层的分治中心为视角的，我们要以上一层分治中心为根求一遍 $size$ 数组（不然就是上上层的 $size$）
点分治的Calc函数
点分治的 Calc 函数很多时候会在子问题范围中进行 dfs 获取信息，然后和数据结构结合，这里举几个例题的例子：
P3806
询问树上距离为 $k$ 的点对是否存在
我们需要首先以分治中心为根进行 dfs，统计出到每一个子树内每一个节点的距离，放入一个数据结构内。
然后我们分别看每一颗子树，考虑这颗子树与它前面的所有子树（看做一个整体）产生的贡献（这是经典的树上小技巧）。显然如果它的距离是 $d$，那么他要查找前面是否出现过 $k-d$
于是我们要支持单点修改（插入距离 $d$），单点查询（查询距离 $k-d$）。这个数据结构很简单，就是数组（或者说桶）
因为直接 memset 会T（事实上点分治内基本不能用 memset，因为容器的大小是树大小，但是单次 Calc 复杂度是子问题大小，memset 会成为时间复杂度瓶颈），所以需要一些小技巧清空数组（记录访问过的下标，可以封装）
还有 P4149 求权值和等于 $k$，且边的数量最小。也是同样的道理，用可清空数组维护，并且不仅要维护有没有对应的路径长度，还要维护经过的边的数量。
例题2
求出最小的k，满足在树中存在路径P，使得 $S \le k \le G$，显然需要维护一个路径长度的有序序列加上二分，对于每一个新的路径 $d$ 二分查找 $k-d$，保留最小值。$G$ 的约束没啥用，最终答案大于 $G$ 则无解（输出 $-1$）
有序序列用 set 维护
例题3
求满足距离 $dist(u,v) <= K$ 的点对个数。（$K$ 范围较小）
基本同板子，因为是区间查询，对于新的路径长度 $d$ 来说,$0 \le d' \le k-d$ 都是合法的，所以用线段树维护
例题4
求满足距离 $dist(u,v) <= K$ 的点对个数。（$1 \le K \le 10^9$）
因为值域很大了，所以说没法用普通线段树维护（动态开点也许可以？），可以考虑平衡树维护。
因为只需要支持 Insert 和 GetRank 操作，用 FHQTreap 写十分简洁。
总结
Calc 一般先是在子问题范围内进行 dfs 获取路径信息，然后对于每一个子树讨论它和前面的子树的贡献，计算完后将信息存进数据结构以便后面的子树计算
易错点
- 如果不在每次找到分治中心后以分治中心为根计算 $size$ 数组，可能会导致复杂度不正确，因为求得重心错误
- 每次计算前要更新当前子问题规模（一般为 $size$ 或者初始的 $n$），并置 $root$ （重心）编号为 $0$，在这种写法下需要令 $mss_{root} = INF$
- Calc时一定要注意分治中心的影响！例如在统计 $k$ 距离点对的时候，应该算上根节点，看作是一条长度为 $0$ 的路径。或者在黑白点染色的时候，必须考虑当前分治中心的颜色，并且不能把这个颜色算在路径长度内（不然两条路径相加会被算两次）
- 注意容器的大小，如果搜索的时候发现已经信息超过了容器大小，就不可能产生答案了，不要把越界信息放进容器。
Comments NOTHING