题解：P12434 [NERC2023] Cactus Transformation

· · 题解

感谢草八牛学长给我推荐的这道题，极大地增强了我的思维能力。以及代码能力。

首先我们可以把本题的仙人掌转化为一种比较通用的形态表示，我将其称之为“大菊花”。点 1 的度数为 n-1，然后其挂着一堆独立的边或者一堆环，这些环全部都是三元环，形如 \{1,a,b\}。为什么不能是四元环五元环？发现我们其实很容易就可以缩减一个环的大小，例如我们现在有一个五元环：

我们可以断开 (3,4) 并连接上 (1,3)，你就可以发现它变成了一个三元环。随后我们再断开 (4,5) 并连接 (1,4)，我们就成功将其变成了“大菊花”：

对于一个 k 元环 \{u_1,u_2,u_3,\dots,u_k\}，我们只需要断开 (u_1,u_k) 并连接 (u_1,u_3)，就会将其变成一个三元环拖着一条链。现在操作完后图中应该会剩下这么一些东西：连着 1 的三元环，连着 1 的单边，通过桥连着 1 的三元环，通过三元环连着 1 的三元环：

前两种情况就是我们想要的，后两者如何处理？对于通过桥连着 1 的情况很好处理（若一个三元环 \{u_1,u_2,u_3\} 通过桥 (u_1,v) 连接至另一个三元环而不是直接连接 1，我们显然可以通过断开 (u_1,v) 并连接 (1,u_1) 转移过来）以图为例，我们断开 (6,7)，连接 (1,6) 就转化成了一个三元环拖着一个链的形式，剩下的部分很好处理。我们接着来看三元连环的情况：

显然，我们一定会剩下一个连接着 1 且度数为 1 的点，否则是无解的。这种情况我们只需要把 (2,3) 断开，连接 (2,6)，就可以转化成桥的情况。至此，所有情况转化完毕，这道题就做完了。

对于无解情况，当且仅当 n 为奇数，\frac{3(n-1)}{2}=m 且两颗仙人掌不同构时无解。理解这个式子不难，除去 1 外的每个点都形成一个三元环，则两个点产生三条边的贡献。此时断边后会发现不论连哪个点都会导致破坏仙人掌的性质，这也是为什么上文提到的三元连环情况一定会存在一个连接着 1 的且度数为 1 的点。题目中的操作显然可逆，那么我们的两个仙人掌必定都能转化为同一个“大菊花”。题目转化为将两个仙人掌转化成同一个“大菊花”，剩下的就是操作次数的限制了。

注意到之前所说的三种情况中，第一二种情况的每次操作必定使得点 1 的度数增加 1，第三种情况必定能通过一次操作转化为第二种情况，不增加点 1 度数。则总操作次数为 O(n)。可以通过本题。

当然，两个仙人掌转化成“大菊花”后肯定会出现编号不同的情况，我们利用单条链转编号就行了，容易看出这样是整体 O(n) 的。

代码在此。

内含少量注释，看不懂的可以评论区咨询。因为是学长一步一步讲的所以可能和学长代码比较相似。

拜谢草八牛。