人类只能做到 $K \le 1.5N$？玩的太差了！这一版可以将最坏情况保证降到
$$ \boxed{K\le\left\lfloor\frac{5N-2}{4}\right\rfloor.} $$
也就是说，主项真正从 $4N/3$ 降到了 $5N/4$，不是继续利用 $N\le40$ 从旧上界里扣一个常数。题目限制 $N\le40$，因此上述取整上界对应的最大比值是 $47/38$。
关键改进是：DFS 最后不返回根，并将切下来的前半块旋转 $90^\circ$，而不是像上一版那样左右翻转。
构造与证明
仍然对输入图建立一棵 DFS 树，根为 $r$，高度为 $H$，高度按边数计算。对同一棵树分别考虑两个构造，选择较小的结果。
第一个构造保留上一版的匹配条带。自顶向下匹配，每个尚未匹配的非叶子与一个儿子匹配；剩下的未匹配顶点都是 DFS 叶子，因而构成独立集。这也是已有 $1.5N$ 构造使用的基本结构。
记匹配数为 $p$，未匹配叶子数为 $\ell$，删去这些叶子后的树直径为 $D$。上一版已经证明并实现的精确边长是 $K_A=N+p-1-\lfloor D/2\rfloor$：沿直径只走一次，其余树边往返；第一对匹配与未匹配叶子特殊处理，其余匹配对各增加两条反对角线。
这里需要的是它关于 $H$ 的界。若 $\ell=0$，则 $D\ge H$；若 $\ell>0$，删去叶子最多使树高减少 $1$，所以仍有 $\ell+D\ge H$。结合 $N=2p+\ell$，得到 $K_A\le\lfloor(3N-H-1)/2\rfloor$。这部分代码保持不变。
接下来改进第二个构造。
先构造一个宽度为 $2H$ 的矩形。
沿用“把祖先写成一行，再按 DFS 游走拼接”的思路。下面使用的具体行定义，额外保证了第一项是当前顶点、最后一项是根，后面旋转拼接要用到这两个性质。
设从根到 $v$ 的路径为 $p_0=r,p_1,\ldots,p_d=v$。构造行 $F(v)$：从 $k=H-1$ 到 $0$，每层追加两个元素 $X,Y$。
当 $k\ge d$ 时，追加 $(v,v)$。否则令 $a=p_k,b=p_{k+1}$：若 $(v,b)$ 是边而 $(v,a)$ 不是边，就令 $X=b$，否则令 $X=a$；若 $(v,a)$ 是边，就令 $Y=v$，否则令 $Y=a$。最后删去整行的第一个元素，再追加根 $r$。行长仍然是 $w=2H$。
这个定义满足以下性质。
行内没有非法接触。 在同一对 $X,Y$ 中，若 $Y=v$，则 $X=a$ 且已确认存在边 $(v,a)$；否则 $X,Y$ 是相同颜色或一对父子。对于相邻两对之间的接触，如果前一对以 $v$ 结束，下一对会根据 $v$ 是否与更高一层祖先相邻，选择该祖先或它的儿子，仍然只产生合法边。
父子对应的两行可以直接上下相邻。 对共同祖先层，$X$ 列的两个取值属于同一对父子，$Y$ 列的取值则分别是该祖先或各自的顶点。两行都选择自己的顶点时，接触的是父子边；只有一行选择自己的顶点时，对应的祖先边已经在定义中确认存在。其余位置也只会出现父子之间或相同颜色之间的接触。
此外，$F(v)$ 的第一项一定是 $v$，最后一项一定是 $r$，而 $F(r)$ 整行都是 $r$。每条非树边都在较深端点对应的行中水平出现。还有一个后面非常关键的细节：若 $v$ 的深度小于 $H$，那么父子边 $(\operatorname{par}(v),v)$ 也一定在 $F(v)$ 中水平出现，因为对应的 $(\operatorname{par}(v),v)$ 那一对没有被删去。
现在选择一个最深的顶点 $t$。从根出发遍历整棵 DFS 树，但将根到 $t$ 的路径留到最后走，并且沿这条路径不再返回。因此，路径外的边各走两次，路径上的边各走一次，得到长度为 $L=2N-1-H$ 的序列 $W$。
依次把 $F(W_i)$ 作为矩形的每一行，就得到一个 $L\times w$ 的合法矩形。所有顶点均出现，非树边在行内出现，树边在游走经过它时出现在第一列。
将前缀旋转 $90^\circ$，放到右下角。
取 $K_B=\max(w,\lceil(L+w-1)/2\rceil)$，并令 $a=\max(0,L-K_B)$、$b=L-a$。将矩形分成前 $a$ 行组成的 $A$ 和后 $b$ 行组成的 $B$。
把 $B$ 原样放在正方形左侧。它的最右列全部是根 $r$；若不足 $K_B$ 行，就复制它的最后一行补齐。
将 $A$ 逆时针旋转 $90^\circ$，放到右下角。旋转前，$A$ 的第一行和最后一列都全部是根，所以旋转后，它的最左列和最上行都全部是根。因此，它的最左列可以与 $B$ 的最右列重叠，右上方没有使用的区域全部填根；若右侧还没有填满，就复制旋转后 $A$ 的最后一列。
这时需要的高度至多为 $\max(b,w)$，宽度至多为 $w+a-1$。由 $K_B$ 的定义，这两个量都不超过 $K_B$。所有新接缝都经过全为根的行或列，不会产生非法边。
代入 $L=2N-1-H$ 和 $w=2H$，得到新的尺寸界：
$K_B=\max(2H,N-1+\lceil H/2\rceil)$。
例如 $N=40,H=20$ 时，这个构造只需要 $49\times49$，而上一版的左右翻转构造会被 $4H-1$ 的宽度卡住。
还必须检查：切开矩形会不会丢边？
切开只移除一处行间边界，所有行内接触都保留，所以不会丢失非树边。
对于树边，根到 $t$ 的路径以外，每条边在第一列至少竖直出现两次，切掉一处边界后仍然保留。根到 $t$ 的路径上，除最后一条进入 $t$ 的边以外，其较深端点的深度都小于 $H$，前面已经证明这些边也有水平表示。
唯一还要关心的是最后一条进入 $t$ 的边。它出现在原矩形的最后两行之间。而 $b=\min(K_B,L)\ge2$，因此最后两行都在 $B$ 中，这条边不会被切掉。
所以，旋转拼接之后仍然保留了输入图的完整边集。
最后合并两个构造。
对任意一棵 DFS 树，都已经有
$$ K\le\min\left( \left\lfloor\frac{3N-H-1}{2}\right\rfloor,\, \max\left(2H,N-1+\left\lceil\frac H2\right\rceil\right) \right). $$
当 $H< N/2$ 时，选择第二个构造。此时 $2H\le N-1$，并且 $N-1+\lceil H/2\rceil\le N-1+\lfloor(N+1)/4\rfloor=\lfloor(5N-3)/4\rfloor$。
当 $H\ge N/2$ 时，选择第一个构造，得到 $K\le\lfloor(3N-\lceil N/2\rceil-1)/2\rfloor=\lfloor(5N-2)/4\rfloor$。
因此，对所有 $N\ge2$，都保证 $K\le\lfloor(5N-2)/4\rfloor$。$N=1$ 单独返回一个格子。在题目的 $N\le40$ 范围内，这个取整上界的最大比值是 $47/38$，对应 $N=38$ 时的边长上界 $47$。
这里不依赖枚举 DFS 根，也不依赖后续压缩成功；固定任意一棵 DFS 树，上界就已经成立。
提交记录：https://qoj.ac/submission/2955547 IOI 题就是简单。