题解：P10632 Normal

· · 题解

我知道你想卷，但你先别急.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。