P17501 [ICPC 2026 Wuhan I] Nailoong vs. Bombloong 2

**这是一道通信题。** 在本题中，你的程序将运行两次。两次运行之间，内存中存储的所有变量都将丢失，但第一次运行中获取的信息可能对第二次运行中正确解决问题非常重要。 本题中有 “奶龙” 和 “暴暴龙” 两个角色。 奶龙拥有一棵包含 $n$ 个节点的树的完整结构信息，而暴暴龙只知道树的节点数 $n$。由于暴暴龙被邪恶的小豹子关起来了，所以奶龙只能通过一种特殊的单向通信方式，来帮助暴暴龙还原出一棵与原树同构的树。 通信的规则如下： - 初始时，树上的所有节点都是白色的。 - 奶龙可以进行 $m \le n-3$ 次操作（$m$ 的值由奶龙自行决定）。 - 在第 $i$ 次操作中，奶龙需要选择树上的一个节点 $x_i$，并反转该节点的颜色（白变黑，黑变白）。 - 每次反转后，定义 $a_i$ 为当前树中两端点颜色不同的边的数量。 - 经过 $m$ 次操作后，奶龙得到了一个长度为 $m$ 的序列 $a_1,a_2,\cdots,a_m$。 奶龙无法直接将节点编号发给暴暴龙，她只能将操作总数 $m$ 以及序列 $a$ 发送给暴暴龙。暴暴龙在收到 $n$、$m$ 以及序列 $a$ 后，需要构造并输出一棵与奶龙的树同构的树。 ## Communication Protocol 每个测试点中，选手程序将被运行两次。在下发文件中，提供了一份测试工具供选手本地调试使用。 ## First Run 在第一次运行中，你将扮演 “奶龙” 角色。 ### Input 输入的第一行包含一个整数 $1$，其作用是让你的程序能够识别这是第一次运行。 第二行包含一个整数 $n$（$4 \le n \le 3\times10^5$），表示树的节点数。 接下来 $n-1$ 行，每行包含两个整数 $u,v$（$1 \le u,v \le n$），表示树上的一条边。 ### Output 输出的第一行应该包含一个整数 $m$（$0 \le m \le n-3$），表示操作次数。 第二行包含 $m$ 个整数 $x_1,x_2,\cdots,x_m$（$1 \le x_i \le n$），依次表示奶龙每次操作反转的节点编号。 ## Second Run 在第二次运行中，你将扮演 “暴暴龙” 角色。 ### Input 输入的第一行包含一个整数 $2$，其作用是让你的程序能够识别这是第二次运行。 第二行包含两个整数 $n,m$（$4 \le n \le 3\times10^5$，$0 \le m \le n-3$），分别表示节点数和奶龙的操作次数。 若 $m>0$，第三行包含 $m$ 个整数 $a_1,a_2,\cdots,a_m$（$0 \le a_i \le n$），表示评测机根据奶龙的操作生成的序列；若 $m=0$，则没有第三行。 ### Output 输出 $n-1$ 行，每行两个整数 $u,v$，表示你还原出的树的一条边（$1 \le u,v \le n$）。你需要保证输出的树和第一次运行中输入的树同构。 ### First Run #### standard input ```text 1 4 1 2 2 3 3 4 ``` #### standard output ```text 1 2 ``` ### Second Run #### standard input ```text 2 4 1 2 ``` #### standard output ```text 1 3 3 2 2 4 ```

无

无

两个样例演示了同一测试点中的两次运行。 奶龙翻转了节点 $2$，此时两端点颜色不同的边的数目为 $2$，故 $a_1=2$。 暴暴龙获得了序列 $a=[2]$，由于暴暴龙和奶龙心有灵犀，所以她一下子就猜到了这棵树的结构。虽然暴暴龙得到的树和奶龙手上的树关于点的编号不同，但他们是同构的，因此仍然算作正确。