树上点对距离问题中，为了去重，有的算法会在子树中减去重复数量。

形式化的，设当前分治树根为 $T$ ，$T$ 的直接子结点树为 $T_1,T_2,T_3,\dots,T_m$ 。

$f(x, y)$ 计算当前分治树根意义下，以 $x$ 为根的树中过 $x$ 且长度 $\le y$ 的点对路径数。

$g(x, y)$ 用尺取法计算当前分治树根意义下，以 $x$ 为根的树中满足 $dis(x, s)+dis(x,t)\le y$ 的点对 $(s, t)$ 数量，即不限制点对在同一个子树中的 $f$。

则 $f(T, k)=g(T, k)-\Sigma_{i=1}^mf(T_i, k-2dis(T, T-i))$

如果不考虑去重问题，算法的主要复杂度在排序上，复杂度上界为

$O(n*\log n+2*\frac{n}{2}*\log \frac{n}{2}+4*\frac{n}{4}*\log \frac{n}{4}+...+n*\frac{n}{n}*\log \frac{n}{n})$

$=O(n*\Sigma_{i=0}^{\log_2 n}\log\frac{n}{2^i})$

$=O(n*\Sigma_{i=0}^{\log_2 n}i)$

$=O(n(\log n)^2)$

$f$ 的是否会导致复杂度超过 $O(n(\log n)^2)$ ? 求证明。