一、 点分治
一、概述
前置知识：数的重心。
假设我们要统计一棵有 \(n\) 个节点的树上所有点对之间距离是 \(k\) 的有多少对。注意树上的边有长度。
\(n\le 10^5,k\le 10^6\)。
一个朴素的算法是遍历树上的所有点对，处理出距离（也就是链的长度）。
时间复杂度 \(O(n^2)\)。
考虑优化。由于只有一次查询，直接求出所有的点对距离太没有必要了。
所以考虑进行分治。
算法流程如下：
-
选择树的重心 \(x\)，它将整棵树分成若干部分，计算所有链中两个端点分别在 \(x\) 的两棵不同子树的贡献。具体来说，遍历 \(x\) 的所有子树，开 2 个桶 \(a\) 和 \(b\)，\(a_i\) 负责装 \(x\) 当前子树里，一个端点为 \(x\) 的长度为 \(i\) 的链有多少条。\(b_i\) 负责装 \(x\) 当前子树之前遍历过的所有子树里，一个端点为 \(x\) 的长度为 \(i\) 的链有多少条。当我们处理完当前子树后，将 \(a\) 桶倒进 \(b\) 桶里，并且将 \(a\) 桶清空。这样可以做到不重不漏。
-
删掉点 \(x\)，继续递归地考虑 \(x\) 的所有子树。
正确性是因为一个在经过其中一级重心的链，不会在上级重心中被算过，也不会在下级重心再被算到。
让我们来分析一下时间复杂度。
首先，由于重心的性质，每次删除全树的重心，最大的子树大小至多为原来的一半。所以一棵有 \(n\) 个节点的树，将被分治 \(\log n\) 层，每一层所处理的所有子树大小之和小于 \(n\)。
所以如果我们可以实现对于每一棵大小为 \(s\) 的子树 \(O(s)\) 处理，我们就可以在总 \(O(n\log n)\) 的时间复杂度内解决这个问题。
处理桶 \(a\) 时，每一次都要用数组记录一个端点为 \(x\)，另一个端点为当前子树中的点的 \(s\) 条链的长度（时间复杂度 \(O(s)\)），然后再把这些链的长度在桶里对应的计数器加一。这样，我们清空桶时直接遍历这些数组，将桶对应计数器清空就行了。所以清空桶的复杂度也是 \(O(s)\)。
那么我们就得到了一个 \(O(n\log n)\) 的做法。
加强版：如果这一题的 \(k\le 1145141919810\) 呢？可以考虑用 2 个 unordered_set（C++ 20）或gp_hash_table 或 gp_hash_table(pbds）代替数组作为桶 \(a\)，\(b\)，或者手写哈希。用 set 或者 map 的话会多一个 \(\log\)，十分不值得。