自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:59:46，当前版本为作者最后更新于2024-06-19 18:12:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我知道你想卷，但你先别急.jpg

容易看出答案就是所有链点数的倒数和。大概就是考虑一个点在点分树上的深度期望，就是一个，把这个点看作根，然后每次随一个点并把这个子树删掉的次数。那么一个点被选中当且仅当他比他的祖先都更早被选中。

接下来我们可以解决实数情形下的带点权的上述问题。这个是经典技巧。

考虑点分治，那么相当于要做一个，支持给 $v$ 对集合 $S$ 求 $\sum_{x\in S} \frac 1 {x+v}$。对于所有 $p=3^k$，记 $\Delta=v-p$，考虑：

$$\sum_{x\in S} \frac 1 {x+p+\Delta}$$ $$\sum_{x\in S} \frac 1 {x+p} \frac {x+p} {x+p+\Delta} $$$$\sum_{x\in S} \frac 1 {x+p} \frac {1} {1-(-\frac {\Delta} {x+p})} $$$$\sum_{x\in S} \frac 1 {x+p} \sum_{i\ge 0}(-\frac {\Delta} {x+p})^i $$$$\sum_{i\ge 0} (-\frac {\Delta} p)^i\sum_{x\in S} \frac 1 {x+p} (\frac p {x+p})^i $$

可以找到 $p$ 使得 $|\frac {\Delta} p|\le 0.5$，于是 $i$ 可以有 $O(\log n\epsilon^{-1})$ 的求和上界。

时间复杂度总计 3log。