P11866 「o.OI R1」na12xy

ForgotMe · 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，可以通过此题。

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