（题面来自luogu）

题目描述

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

输入格式

N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k

输出格式

一行，有多少对点之间的距离小于等于k

　　原本是点分治的模版题，从昨晚调到今晚……这里记录下点分治实现时需要注意的几个细节。

1、分治过程中递归子树大小的确定

　　以下是点分治过程的核心函数，其中cur表示以u为根进行分治的树的大小。

1. void Divide(int u) {

2. vis[u] = true;

3. ans += Solve(u, 0);

4. int tcur = cur;

5. for (int i = head[u]; i; i = edge[i].nxt) {

6. int v = edge[i].to;

7. if (vis[v]) continue;

8. ans -= Solve(v, edge[i].w);

9. Mn = inf;

10. //cur = size[v];

11. cur = size[u] > size[v] ? size[v] : tcur - size[u];

12. Find_rt(v, u);

13. Divide(root);

14. }

15. }

    　　重点在第10、11行递归子树大小确定的两种写法，其中第11行未注释的版本是正确的。考虑到我们每次在当前树中选重心为根进行分治，那么u并不一定是该树在搜索树意义下的根节点。也就是说，u的子节点v有可能是u在搜索树上的父亲，因此在确定递归子树大小时加入一个特判。因为cur的值会因为遍历先前的v而改变，我们在第4行用一个新变量记录当前树的大小。这个就是调了一天的锅的出处

    　　（不过据说不加这个判断复杂度也不会劣化……貌似还有人证明了，不过保证正确性显然是好的）

2、关于点分治两种写法的优劣

　　点分治不同写法的讲解请见我的博客：https://www.cnblogs.com/TY02/p/11203163.html

　　之前认为用容斥算两遍的做法常数过大，比较起来把子树分开互相统计更好。实际上第二种做法有它的局限性：例如在这个题中，暴力枚举每条路径会T飞，我们只能把u子树中所有的节点深度都统计一遍，排序后利用单调性用双指针统计答案。这就暴露了分子树统计的劣势，它只可以把子树中两点不重不漏地两两枚举、组合路径信息，无法在其中嵌套别的操作。容斥的优点在于它把所有的节点信息一次性统计出来，适合类似本题利用数据单调性排序来统计的情形。这个题也不排序也可以用权值树状数组来做，复杂度相同，常数因为要清空数组会大一些。

完整代码：