user100566 @ 2024-11-07 08:57:37
树上点对距离问题中，为了去重，有的算法会在子树中减去重复数量。
形式化的，设当前分治树根为 T ，T 的直接子结点树为 T_1,T_2,T_3,\dots,T_m 。
$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)