P15416 "yrOI R1" Summer Has Passed


You are given two trees $S, T$ of size $n$. Define one operation on $S$ as follows: - Choose any diameter $(p, q)$ of $S$. - Choose any node $u$ **on this diameter**, then choose a node $v$ adjacent to $u$ that is **not on this diameter**, then choose another node $w$ **on this diameter**, and perform: - Delete the edge $(u, v)$, and add the edge $(v, w)$. You need to determine whether it is possible to apply the operation any number of times to transform $S$ into some $S'$, such that $S'$ is isomorphic to $T$. If it is possible, you need to output one valid plan within $4n$ operations.

The first line contains a positive integer $n$, which is the size of trees $S$ and $T$. The next $n - 1$ lines each contain two integers $(a_i, b_i)$, representing an edge of tree $S$. The next $n - 1$ lines each contain two integers $(c_i, d_i)$, representing an edge of tree $T$.

Output a string $\texttt{Yes}$ or $\texttt{No}$ on the first line, indicating whether it is possible to make $S$ isomorphic to $T$ using the operations. If you output $\texttt{Yes}$, then on the next line output an integer $k$, the number of operations in your constructed plan. You must ensure that the number of operations is at most $4n$. If your number of operations exceeds $4n$, you will be judged as Wrong Answer. In the next $k$ lines, output five integers $(p_i, q_i, u_i, v_i, w_i)$, describing one operation. Then you need to output one line $p_i$, meaning that in the tree $S$ after all operations, node $x$ corresponds to node $p_x$ in tree $T$. This problem uses a Special Judge. If you correctly output $\texttt{Yes}$ or $\texttt{No}$, you will get $20\%$ of the score for that subtask. Note: if you output $\texttt{Yes}$, you must output a plan afterwards (even if it may be invalid; you can directly output $n + 1$ zeros to do this).

**This problem uses bundled testdata**. - Subtask 1 (5 pts): $n \le 10$. - Subtask 2 (5 pts): $S$ is a path. - Subtask 3 (5 pts): $T$ is a path. - Subtask 4 (5 pts): $S$ is a star (also called "juhua", 菊花). - Subtask 5 (10 pts): $S$ and $T$ each have only one diameter, and all nodes with degree $> 2$ exist only on the diameter. - Subtask 6 (10 pts): The initial diameters of $S$ and $T$ have the same length. - Subtask 7 (25 pts): $n \le 500$. - Subtask 8 (35 pts): No special constraints. For $100\%$ of the data, $1 \le a_i, b_i, c_i, d_i \le n \le 2 \times 10^3$. ----------------- When all journeys end, and I fall into sleep. I will surely return to this summer. Translated by ChatGPT 5