自动搬运

查看原文

来自洛谷，原作者为

	ForgotMe 花与剑无痕，高挂一轮明灯。银蝶染旧梦，生死莫再问。

搬运于2025-08-24 23:10:56，当前版本为作者最后更新于2025-03-08 21:32:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

破防了，写了一下午的乱搞，也不知道自己最后在写什么玩意，反正最后 sub1 tle 3 个点喜提 0 分！

如果你一上来就跟我一样考虑从剥叶子去做，那么基本上就做不出来了，甚至你会怀疑这题是否可做，怎么可能只用这么少的空位。

不如从一条链开始考虑，这是简单的，显然只需要两个空位就可以做。但是实际上链上的每个点可能会挂着若干个子树，假设这条链的顺序是 $u_1,u_2,...,u_k$，那么先给 $u_1$ 留一个空位放进去，然后使用某种策略先把 $u_1$ 挂着的所有子树给构建出来（显然一旦构建出来后，所占据的所有空位都可以释放出来），这是一个子问题，接着扫到 $u_2$ 时把 $u_1$ 和 $u_2$ 连起来，并将 $u_1$ 占着的空位释放出来，依次这么做，可以发现如果设 $F_n$ 表示大小为 $n$ 的的树所需的空位数量，那么 $F_n=F_{mx}+1$，其中 $mx$ 为链上挂着的子树大小最大值。

现在问题变为选出树的一条链，让 $mx$ 尽量的小。显然你可以选一条经过重心的链，从而让 $mx$ 为 $\dfrac{n}{2}$ 的级别，这样可以做到 $F_n=\log_2 n$，显然无法通过。实际上可以做到更优，考虑选出重心，以及其最大子树的儿子对应的重链，次大子树的儿子对应的重链，三段拼起来。设 $S_1,S_2,S_3$ 分别表示最大子树的大小，次大子树的大小，以及剩下子树大小的最大值。那么根据重儿子的性质以及重心的性质 $\dfrac{n}{2}>S_1>S_2>S_3$，$mx=\max(\dfrac{S_1}{2},\dfrac{S_2}{2},S_3)$。那么在最坏情况下 $S_1=S_2=S_3=\dfrac{n}{3}$，$mx=\frac{n}{3}$，得到 $F_n=\log_3 n$，可以通过此题。

代码就不放了，模拟上述思路即可。