题解：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