题解：P13537 [IOI 2025] 世界地图（worldmap）

· · 题解

我咋这么唐呢。

首先有一个自然的想法是，取出一个生成树，想一个比较好看的树的构造，然后每个节点额外塞一些非树边。

树的情况考虑这样的构造：

如果我们取出的是 DFS 树，那非树边一定是祖孙关系，我们把它放到深度较低的点上，每个点就最多只需要连 sz_u-2 条非树边，而点的宽度是 2sz_u-1 的，也就是非树边可以在每个节点顶上这条一个隔一个地放：

这样我们就做到了 3n\times 2n，可以获得 86 分。

vp 的时候我注意到放在一侧也可以做到 3n\times 3n，考虑平衡一下这两个东西：出栈序前 \frac 3 4 n 个点放在上面，高度不会超过 2.5n；其他点放在侧面，宽度不会超过 2.5n 且高度只会对 2sz+\frac 1 4 取 \max，可以获得 93 分。code

但是我们观察到一个惊人的性质：题目中说的相邻是有公共边不是有公共点！！！考虑这样的构造：

轻松做到 2n\times 2n，可以获得 100 分。code