题解：P8004 Welcome to Lunatic City

· · 题解

感觉是一个 \mathcal O(n) 做法。

下文中 deg 指以 1 为根儿子个数。

问题可以转化为构造另一棵以 1 为根的树，使得每个点的 deg 不变，且所有关键点的深度之和最小。转化过程略去。

首先是一个结论：将所有点按以度数为第一关键字，是否为关键点为第二关键字排序得到 p_1,p_2,\dots,p_n（钦定 p_1=1） 那么一定存在一个 1\le k\le n，使得最优答案由保留 p_{1\sim k}，将 p_{k+1\sim n} 按照以是否为关键点为第一关键字，度数为第二关键字重排后得到的排列取到。也就是依次填完 p_{1\sim k} 后接着填剩下的所有关键点，再填剩下的非关键点。

证明考虑如果这样取不到最优，最优的树长什么样。可以发现会存在第 i 层一个关键点 x，第 i+1 层一个非关键点 y 使得 deg_y>deg_x，且第 \ge i+2 层存在关键点。此时交换 x,y（原来 x 的子树都接在 y 下面，y 的前 deg_x 个子树接在 x 下面），只有一个关键点深度 +1，如果 y 的后 deg_y-deg_x 个子树中有关键点则调整不劣，否则将其中任意一个子树和 \ge i+2 层的关键点交换也不劣。

考虑枚举 k 求答案，设现在的树在第 d 层还有 y 个空位，第 d+1 层还有 x 个空位，现在需要求出将 p_{k+1\sim n} 中的关键点依次填进去后他们的深度和。

先把前 y 个填进去，得到 x^{\prime} 个都在 d+1 层的空位。接下来考虑暴力：先把前 x_0=x^{\prime} 个点填在 d+1 层，设 x_1 为他们的度数和，则 d+2 层有 x_1 个空位，再填接下来的 x_1 个点，然后得到 x_2，以此类推。

考虑优化。可以发现，在填入 deg\le 1 的关键点之前，都有 x_i\ge 2x_{i-1}，所以这样至多填 \log\frac{n}{x_0} 层，而后面度数均为 1,0 的部分是容易 \mathcal O(1) 算的。而且可以认为，p_{2\sim k} 度数都不小于 2，所以有 x_0=x^{\prime}\ge k，那么这部分总复杂度为 \sum_{k=1}\mathcal O(\log\frac{n}{k})=\mathcal O(n)。

这里的复杂度分析是：

\sum_{k=1}\log\frac{n}{k}=\sum_{i=1}\sum_{k=1}[\log\frac{n}{k}\ge i]=\sum_{i=1}\frac{n}{2^i}=\mathcal O(n)

前面的排序和后面的构造容易线性，故总复杂度 \mathcal O(n)。