先开个坑...
之前学过点分治，但是总是感觉打的时候内心莫名的慌，敲完几个函数的定义就开始脑袋一片空白。
所以重学了一下点分治，并写了这篇博客。
看看什么时候把它补完吧。
找了两篇还不错的博客
https://www.cnblogs.com/bztMinamoto/p/9489473.html
https://www.cnblogs.com/PinkRabbit/p/8593080.html
考虑这样一个问题：给出一棵树，求有多少个点对 \((x,y)\) 满足它们之间的距离不超过 \(k\) / 等于 \(k\) / 大于 \(k\)。
\(1 \le n \le 10^5\)
很显然，求两个点点对数目，可以枚举这两个点，然后求它们的距离。
时间复杂度 \(O(n^3)\) ，如果命题人给了这个复杂度超过 \(20pts\) 可真是良心。
可以枚举起点 \(x\) ，然后遍历这棵树，一旦距离超过 \(k\) 就返回。
如果是求大于 \(k\) 的，就先求出小于等于 \(k\) 的，然后容斥。
时间复杂度 \(O(n^2)\) ，正常的命题人应该会给到 \(30pts-60pts\) 。
点分治。
点分治，顾名思义，是一种与点有关的分治算法。
原文：https://www.cnblogs.com/liubainian/p/11777125.html