P15419 「yrOI R1」冬日永恒


我们对一个森林集合定义一次操作为，选择 $k$ 个互不相同的点 $u_{1 \sim k}$（如果不能选择则不能操作），然后依次进行以下流程： + 建立一个新点 $n'$，对 $i \in [1, k]$ 连边 $(n',u_i)$。你需要时刻保证目前存在的点的个数 $\le \max(n_1,n_2)+5$。 + 如果当前的图中存在环，你可以选择一个简单环并删除它上面所有的边，重复此流程直到没有环存在。 + 删除所有度数为 $0$ 的点。 现在，给你两棵树 $S,T$，$n_1=|S|,n_2=|T|$，你需要判断，$G=\{S\}$ 能否进行若干次操作得到森林集合 $G'$，$G'$ 只包含一棵树 $S'$，并且 $S'$ 与 $T$ 同构。 由于出题人非常善良，你可以进行 $m$ 次操作，$m$ 见数据范围。

第一行输入两个数 $c,t$，代表测试点编号和数据组数。特别地，样例中 $c=0$。 接下来输入 $t$ 组数据： 第一行输入三个数 $n_1,n_2,k$，代表 $S,T$ 树的大小和 $k$。 接下来 $n_1-1$ 行每行输入一条边 $(u_i,v_i)$，代表树 $S$ 的一条边。 接下来 $n_2-1$ 行每行输入一条边 $(x_i,y_i)$，代表树 $T$ 的一条边。

你需要输出 $t$ 组数据的答案： 第一行输出一个字符串 $\texttt{Yes}$ 或者 $\texttt{No}$，代表是否可以让 $S$ 通过操作与 $T$ 同构。 如果你输出了 $\texttt{Yes}$，接下来一行你需要输出一个数 $r$，代表你构造方案的操作次数。 你需要保证你的操作次数小于等于 $m$ 次，如果你的操作次数超过了 $m$，将会被判定为 Wrong Answer。 接下来你需要输出你进行的 $r$ 次操作： 第一行输出 $k$ 个数，代表你选择的点，接下来在 $k$ 个点后面输出一个数 $n'$，代表你新建的点。注意：$n'$ 必须曾经被删除过或者从未出现于 $G'$。你需要保证 $n' \le \max(n_1,n_2) + 5$。 接下来输出一个整数 $l$，代表你删除的简单环个数，接下来 $l$ 行每行描述一个删除的简单环，第 $i$ 行首先输出环的长度 $h_i$，接下来输出一个顶点序列 $u_{1 \sim h_i}$ 代表你删除的环，请注意，必须按任意一种环上的方向依次输出 $u_{1 \sim h_i}$。 最后你需要输出一行 $p_x$，代表操作后的 $S'$ 树中 $p_x$ 对应 $T$ 树的 $x$。 本题开启 Special Judge，如果有多种方案，输出任意一种即可。如果你的方案不合法，将会被判定为 WA/UKE。

本题开启子任务测试，但是不绑点。记 $N = \max(n_1,n_2)$。 + Subtask 1（20 pts）：$k=2$。 + Subtask 2（40 pts）：$k=3$。 + Subtask 3（40 pts）：$k=4$。 每个子任务有 $20$ 个测试点，每个测试点等分获得该子任务的分数。记 $N_{\max}$ 为 $N$ 的最大可能值，二十个测试点的 $\{N_{\max}\}=\{3,5,8,20,50,100,300,500,700,1000,1000,1000,1000,2 \times 10^4,4 \times 10^4,6\times 10^4,8 \times 10^4,10^5,10^5,10^5\}$。 第 $i$ 个子任务的第 $j$ 个测试点编号为 $20(i-1)+j$。 对于每个 subtask 的第 $1 \sim 13$ 个测试点：$1 \le T \le 10^3$，$2 \le n_1,n_2 \le 10^3$，$k \in \{2,3,4\}$，$\sum N^2 \le 10^8$。 对于 $100\%$ 的数据：$1 \le T \le 10^3$，$2 \le n_1,n_2 \le 10^5$，$k \in \{2,3,4\}$，$\sum N \le 5 \times 10^5$。 $m=m_0+10$，$m_0$ 见下表： | 测试点编号 | $m_0=$ | |:-:|:-:| | $1 \sim 13$ | $2.0 \times 10^3$ | | $14 \sim 20$ | $2.0 \times 10^5$ | | $21 \sim 33$ | $1.0 \times 10^3$ | | $34 \sim 40$ | $1.0 \times 10^5$ | | $41 \sim 53$ | $1.25 \times 10^3$ | | $54 \sim 60$ | $1.25 \times 10^5$ | ------------ 「我觉得...只有在什么结束的时候，才能开始达到永恒」‌