IOI2025《世界地图》$K=\frac{4}{3}n+O(1)$ 的做法

首先本题原本的做法是 \(K=2n\) 的，之后 zky 提出了一个 \(K=1.5n\) 的做法：https://chuna2.787528.xyz/zkyJuruo/p/19023079，本文是对 zky 做法的改进。

可以在 https://uoj.ac/submission/826890 看代码。

\(K=2n\)

先找到原图的一棵 dfs 树，然后取 dfs 树的欧拉环游序，斜着放在矩阵中：

1234
2343
3432
4321

然后我们加入非树边。考虑在某次访问到点 \(x\) 时，加入 \(x\) 向祖先的反祖边。这只需要构造一个夹层，然后祖先放进去就好了：

   x.x
  x.x
 x.x
x.x

（. 的位置可以放祖先）

然后注意到在这次访问 \(x\) 前后都会访问 \(x\) 的所有祖先，因此夹层的大小至少为祖先个数，那么就一定可以放进所有祖先。

我们需要 \(4n\) 条斜线，因此 \(K=2n\)。

\(K=1.5n\)

对每个点都用两条斜线构造一个夹层是比较浪费的，考虑优化，一个想法是我们可以合并两个夹层：

  x
 x.
xxx
y.y
.y
y

（每种列都可以使用任意次）

可以发现，对于一个点 \(z\)，无论是要连 \(x\)，\(y\) 还是 \(x\) 和 \(y\)，在上述夹层中都只需使用一列。这样就将两个夹层合并为了一个夹层，并且省去了一条斜线。

考虑在 dfs 树对相邻点做一些匹配，从上往下，每次取一个点没匹配的点，匹配其的最后一个儿子。这样会形成若干组匹配，和一些失配的叶子。

对于一组匹配，我们用上述方法把它们的夹层合并，注意到需要放的还是它们的祖先，因此夹层大小的需求并没有变大。

但我们还需处理叶子。注意到叶子间是不会有连边的，因此考虑把叶子向祖先的连边放在祖先处处理，这样我们在欧拉环游的过程中也就不需要访问叶子了。

那么现在一组匹配的夹层需要放下它们的所有祖先，以及子树内所有失配的叶子。祖先当然还是放得下的；对于失配叶子，由于我们欧拉环游时没有访问它们，因此省下了两条斜线，那么我们可以在最前和最后均添加失配叶子个数条空斜线，于是失配叶子也就可以放得下了。

这样需要 \(3n\) 条斜线，因此 \(K=1.5n\)。

\(K=\frac{4}{3}n+O(1)\)

类似上面的想法，考虑把三个夹层合并为一个夹层。

	 x
    x.
   x.x
  xyz.
 xyz.z
xy.yz
.yyz
yyz
.z
z

可以发现，对于一个点 \(o\)，无论是要连 \(\{x,y,z\}\) 中的哪个子集，也都只需要一列。并且相对于上面的做法，又省掉了一条斜线。

考虑在 dfs 树上进行长度为 3 的链剖分，在欧拉环游时，我们最后访问一个点的实儿子，并在回溯一条链时构造上述夹层。

现在一个夹层需要放下三元链的所有祖先的连边，以及子树内不在链剖分中的所有点向其的连边。同时还需要 \(O(1)\) 的额外大小，这个直接在前后加 \(O(1)\) 条空斜线即可。

如果我们直接欧拉环游整棵树，并进行上述构造。那么祖先直接放肯定是可以放下的，但是子树内不在链剖分中的点直接放就不一定放得下了。因为对不在链剖分中的点不构造夹层只省下了 \(\frac{2}{3}\) 条斜线，这就可能导致夹层后方的斜线条数不足。

考虑进行更精细的分析，一个不在链剖分中的连通块有两种形态：叶子、一些叶子与它们的父亲构成的菊花。下面进行分类讨论：

• 叶子

  这个还是一样的，我们在欧拉环游时可以不访问它，这样就省下了 2 条斜线，于是在最前和最后都添加一条空斜线，那么这个叶子在祖先的夹层中就可以放下了。

• 菊花

  这里再把菊花分为一个叶子的菊花（也就是一条边）和至少有两个叶子的菊花。

  • 至少有两个叶子的菊花

    对于这样菊花，我们可以优化欧拉环游时遍历它们所需的斜线数。

    方法是不进行欧拉环游，而是直接构造一个夹层：

     xc
    xbx
    ax
    
    （假如菊花根为 x，叶子为 a,b,c，上述构造就完成了 x 对 a,b,c 的连边）
    

    先判掉整棵树是一个菊花的情况，那么走到菊花的根时至少可以构造大小为 \(3\) 的夹层。

    我们使用大小为 \(2\) 的夹层和大小为 \(3\) 的夹层，假设菊花大小为 \(k\)，我们仅需不超过 \(k+1\) 条斜线就可以达到对该菊花欧拉环游的效果。这样就省下了至少 \(k-1\) 条斜线，同时不对该菊花构造夹层又省下了 \(\frac{2k}{3}\) 条斜线，因此可以在最后添加 \(k\) 条空斜线以保证祖先的夹层中可以放下这个菊花。

  • 边

    这种情况就不能用上述方法节省斜线了，但我们还可以用其它方法。

    假设这两个不在链剖分中的点为 \((a,b)\)，考虑取出一个三元链 \((x,y,z)\)，使得 \(a,b\) 均向 \(a,b,c\) 有连边。

    如果不存在这样的 \((x,y,z)\)，说明对于任意三元链，只需要放下 \(a,b\) 中的至多一个。那么我们在欧拉环游时访问 \(a,b\)，就可以保证三元链前方有足够斜线，同时不对 \(a,b\) 构造夹层省下了 \(\frac{4}{3}\) 条斜线，因此在最后加入一条空斜线，即可保证三元链后方也有足够斜线。

    如果找到了这样的 \((x,y,z)\)，我们考虑不在欧拉环游时访问 \(a,b\)，而是在访问链 \((x,y,z)\) 时加入边 \((a,b)\)，并且只用 \(3\) 个额外夹层。

    如果上述目标可以达成，那么对于一个要放入 \(a,b\) 的三元链，我们还是会在访问三元链前访问 \(a,b\)，因此前方斜线数是够的。

    同时由于我们加入边 \((a,b)\) 时省下了 \(1\) 条斜线，同时不对 \(a,b\) 构造夹层省下了 \(\frac{4}{3}\) 条斜线，因此可以在最后添加两条空斜线以保证三元链后方的斜线数足够。

    现在考虑一个三元链 \((x,y,z)\)，我们需要在访问 \((x,y,z)\) 时加入一些边 \((a,b)\)，下面进行分类讨论：

    • 如果 \(a,b\) 同时向三元链中的同一个点有连边。比如 \(x\)，那么我们把访问 \(x\) 的斜线替换为 \(x,a,b,x\) 四条斜线，就可以添加边 \((a,b)\)。

      这样的替换可以进行任意次，因此就能解决所有向三元链中同一个点有连边的 \(a,b\)。

    • 对于 \((a_1,b_1)\) 和 \((a_2,b_2)\)，如果 \(a_1,a_2\) 向三元链中同一个点有连边，\(b_1,b_2\) 向三元链中的同一个点有连边。比如存在边 \((x,a_1),(x,a_2),(y,b_1),(y,b_2)\)，那么把访问 \(x\) 的斜线替换为 \(x,a_1,b_1,y,b_2,a_2,x\) 七条斜线，就可以添加边 \((a_1,b_1),(a_2,b_2)\)。

      由于边是无向的，因此 \(a_1,b_2\) 向三元链中同一个点有连边，\(b_1,a_2\) 向三元链中的同一个点有连边的情况也可以解决。

      这样的替换也可以进行任意次，最终可以使得，对于任意 \((x,y,z)\) 中的点 \(p,q\)，存在边 \((a,p),(b,q)\) 或者 \((a,q),(b,q)\) 的边 \((a,b)\) 至多只剩一条。

      最后会剩至多三条边，不妨令它们为 \((a_1,b_1),(a_2,b_2),(a_3,b_3)\)，存在边 \((a_1,x),(b_1,y),(a_2,y),(b_2,z),(a_3,x),(b_3,z)\)。下面进行分类讨论：

      • \((a_3,b_3)\) 存在

        • \((a_1,b_1)\) 存在

          • \((a_2,b_2)\) 存在

            把访问 \(y\) 时的斜线 \(y\) 替换为 \(y,b_1,a_1,x,a_3,b_3,z,b_2,a_2,y\) 即可。

          • \((a_2,b_2)\) 不存在

            把访问 \(z\) 时的两条斜线 \(y,z\) 替换为 \(y,b_1,a_1,x,a_3,b_3,z\) 即可。

        • \((a_1,b_1)\) 不存在

          把访问 \(y\) 时的两条斜线 \(x,y\) 替换为 \(x,a_3,b_3,z,y\) 即可。

          如果存在 \((a_2,b_2)\)，就把访问 \(z\) 时的两条斜线 \(y,z\) 替换为 \(y,a_2,b_2,z\) 即可。

      • \((a_3,b_3)\) 不存在。

        如果存在 \((a_1,b_1)\)，就把访问 \(y\) 时的两条斜线 \(x,y\) 替换为 \(x,a_1,b_1,y\) 即可。

        如果存在 \((a_2,b_2)\)，就把访问 \(z\) 时的两条斜线 \(y,z\) 替换为 \(y,a_2,b_2,z\) 即可。

    这样就完成上述目标了。

综上所述，我们只需要 \(\frac{8}{3}n+O(1)\) 条斜线，因此 \(K=\frac{4}{3}n+O(1)\)。

（代码中取 \(K=\frac{4}{3}n+2\) 通过了，我不太知道常数只取 \(2\) 是否足够。）

期待大家提出更进一步的做法！