提交记录

点分治按照重心递归的时间复杂度应为 $O(n \log n)$的。然后分析时间复杂度的重点应在于我代码中的 $Calc$ 时间复杂度。问问佬们分析的对不对。

以下为我自己分析的过程。

考虑最坏情况。
每次分别会找 $1,2,4,8, ...$ 个 重心，那么可以通过等差数列求和公式算出调用 $Calc$ 函数的次数级别应该为 $O(n)$。

再看它本身的复杂度。

因为我们本质是在分治，所以在同阶的情况下（比如此时需要遍历树的大小为 $n/2$，遍历两次），所以每同阶次 $Calc$ 中遍历树的部分应该总体为 $O(n)$ 的，显然有 $\log n$ 个同阶次。
然后我的代码 $dfs$ 函数中遍历到每个点都会遍历一遍询问，也就是复杂度还要乘 $m$。

所以代码总体时间复杂度为 $O(n \times m \times \log n)$。可以通过此题。

各位佬们，我扯得合理嘛/kel