下文可能会出现一些把点分治叫成淀粉质的情况。
事情都要从学长让我写一些神秘题开始说起，然后发现我不会点分治了，于是严肃加训。
基础
首先考虑分治是一个什么东西。就是每次找一个端点，然后计算跨端点的贡献。同时，选择的这些端点具有某些特殊性质，以保证递归层数不会太多，进而每层内可以遍历区间内所有元素，去计算一些信息。
不难发现，这样计算是不重不漏的（可能需要特判 \(l=r\) 的贡献，这个一定不能忘记）。
在树上，我们也可能会遇到一些这一类的问题，那么，我们能不能把这种策略搬到树上呢？
显然是可以的。下面我们引入一些例题。
P4178
计算点对数量这个东西，按照上面的策略来说，我们应该让它跨过已些东西计算，同时保证跨的这些点有一些良好性质。
于是，对于一个分治中心 \(u\)，我们只去计算跨过 \(u\) 的点对的贡献。同时，为了防止出题人给我们一条链把我们创飞，我们需要每次选择子树内重心当作分治中心。
接下来考虑在每一层内把所有点待算点全都挖出来，然后按距离排序，夹逼双指针即可。这样是两只 \(\log\) 的，显然能过。
这里显然你不能选择自己和自己作为一个点对，所以不需要特判。
代码细节非常多，可以参考实现（虽然好像没 AC 看不到，但是扔剪贴板里可能被我哪天删了（））。
也许是一份参考实现