自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:32:32，当前版本为作者最后更新于2021-07-17 21:44:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

第 1 步：我们首先将问题进行第一步抽象：答案只和叶子的深度构成的多重集相关。

我们考虑进行一次操作之后对于度数集合的影响：原多重集为 $S$，将一个深度为 $d$ 的节点进行替换之后，会生成一族深度为 $S+d$ 的叶子，并且失去一个原先的深度为 $d$ 的叶子。

第 2 步：将多重集写作 GF，观察形式。

设原来的多重集的 GF 为 $S(x)$，新生成的一组叶子就是 $x^d S(x)$，最后要删去一个深度为 $d$ 的叶子，那么最后的集合就是 $(1+x^d)S(x) - x^d$。

第 3 步：猜想相邻两次替换操作交换不影响答案。

为了验证，我们尝试写出来接连替换两个深度分别为 $d,e$ 的叶子会发生什么：

$$(1+x^e)[(1+x^d)S(x) - x^d] -x^e = (1+x^e)(1+x^d)S(x) - x^e -x^d - x^{d+e} $$

右式关于 $d,e$ 对称，显然交换。并且右边的形式诱导我们写成更加漂亮的样子：

$$(1+x^e)(1+x^d) S(x) - (1+x^e)(1+x^d) + 1$$

第 4 步：

设深度为 $i$ 的叶节点被替换了 $a_i$ 次，前面的推导引导我们知道这样一个无穷序列能消去任何深度有限的叶子，当且仅当

$$(S(x)-1) \prod _{i\ge 1}(1+x^i)^{a_i} + 1 = 0$$

移项可得

$$\prod _{i\ge 1}(1+x^i)^{a_i} = (1-S(x))^{-1}$$

第 5 步：

对于左式这种变换我们已经很熟悉了，两边取对数，有

$$\sum_{i\ge 1} a_i \ln (1+x^i) = \ln \frac 1{1-S(x)} $$

也即

$$\sum_{ij=k} a_i \cdot \frac{(-1)^{j-1}}{j} = [x^k]\ln \frac 1{1-S(x)} $$

左式直接从小到大反解，复杂度为 $\Theta(n\log n)$，亦可根据各维独立性做到 $\Theta(n\log\log n)$。

右式可以做到 $\Theta(n\log n)$。

$S(x)$ 可以 $\Theta(n)$ 得到。

本问题在 $\Theta(n\log n)$ 内解决。