CF2215C Oriented Journey

- 这是一个通信题。 - 本题不允许 Hack。

游戏有两位玩家：玩家 A（Neri）和玩家 B（Mashiro）。裁判会先和玩家 A 交互，玩家 A 结束后，裁判再和玩家 B 交互。注意，玩家 A 和玩家 B 之间不能直接传递信息；他们只能和裁判单向通信，但可以事先商量好交流策略。 在交互开始前，裁判会确定一个大小为 $n$ 的无向树 $T$ 和一个整数 $s$（满足 $1 \le s \le 2^{n-1}$）。这两个值对两位玩家都是一样的。 玩家 A（Neri）首先从裁判那里拿到两个整数 $n$ 和 $s$，但对树 $T$ 一无所知。接下来，裁判会和 Neri 交互 $n-1$ 轮，每轮交互： - 裁判会告诉 Neri 树 $T$ 中的一条无向边，Neri 必须 **立刻** 给这条边指定一个方向。 注意，经过这 $n-1$ 轮交互后，树 $T$ 的所有边都被赋予了方向，形成一棵新的有向树 $T'$。 玩家 B（Mashiro）收到这个有向树 $T'$，她的任务是根据这棵树判断出整数 $s$。 Neri 的目标是确保 Mashiro 能正确推断出 $s$。你的任务是扮演两位玩家，设计一套最优的交互策略，让 Mashiro 能准确地确定 $s$。 ## 第一次运行 你的程序会对每个测试点运行两次。第一次运行时，你是玩家 A（Neri）。 ### 输入格式 第一行包含两个整数 $t$ 和 $q$（$1 \le t \le 10^4$，$q=1$）——测试点数量和运行次数。这里给出 $q=1$ 是为了让程序知道这是第一次运行，应扮演玩家 A（Neri）。 每个测试点，先读入两个整数 $n$ 和 $s$（$3\le n \le 30$，$1\le s \le 2^{n-1}$）——树的大小和要传递的整数。 ### 交互规则 对于每个测试点，你先从输入读入 $n$ 和 $s$。然后，需要和裁判交互 $n-1$ 轮： - 先从裁判读入两个整数 $u$ 和 $v$（$1\le u < v\le n$），表示树 $T$ 中有条无向边 $(u,v)$； - 接着，输出两个整数 $a$ 和 $b$，用空格隔开，表示你给这条边指定的方向。$(a,b)$ 要么是 $(u,v)$，要么是 $(v,u)$。输出 $(a,b)=(u,v)$ 表示方向是 $u \rightarrow v$，输出 $(a,b)=(v,u)$ 表示方向是 $v \rightarrow u$。 注意，你必须在得到下一条边的信息之前，**立刻**给当前边定向。 完成所有测试点后，程序结束。 交互器是 **非自适应的**，也就是说每个测试点的树 $T$ 在交互开始前就固定好了。 每轮交互结束后，别忘了换行并刷新输出，否则会因为“空闲时间超限”判错。 如果在任何交互步骤读到 $-1$，说明交互出错，你的程序必须立刻退出。否则会因为继续读关闭的流导致不可预料的判决。 ## 第二次运行 第二次运行时，你是玩家 B（Mashiro）。 ### 输入格式 第一行包含两个整数 $t$ 和 $q$（$1\le t\le 10^4$，$q=2$）——测试点数量和运行次数。这里给出 $q=2$ 是为了让程序知道这是第二次运行，应扮演玩家 B（Mashiro）。 每个测试点的第一行包含一个整数 $n$（$3\le n \le 30$）——树的大小。 接着有 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1\le u,v\le n$），表示树 $T'$ 中有条有向边 $u \rightarrow v$。 注意，第二次运行的测试点顺序可能被 **打乱**。具体请看示例。 ### 输出格式 每个测试点输出一个整数 $s$——你根据有向树 $T'$ 推断出的整数。 输出后别忘了换行并刷新输出，否则会因“空闲时间超限”判错。然后处理下一个测试点，或者结束程序。

无

无

### 样例解释 第一轮示例：Neri 收到的 $s$ 分别为 $s=21$ 和 $s=59$。根据两方约定的策略，Neri 对树进行了定向。  第二轮示例：请注意两轮的测试用例顺序可能被重排。可参考下列 $T'$ 的可视化图示：  ### 测试工具 你可以使用命令行工具在本地进行测试。具体下载方式请见题目所附材料。 使用该工具需安装 Python。在终端使用如下命令启动： - Windows：`python treedir_testing_tool.py [–quiet] ` - Linux：`python3 treedir_testing_tool.py [–quiet] ` **参数介绍**： - `-q`, `–quiet` ：该参数可选，加上后测试工具不会打印交互日志。 - `data_file` ：是你准备的数据文件，需满足如下格式： - 第一行两个整数 $t$ 和 $s$ 表示测试用例数量和用于随机打乱顺序的种子，$s=0$ 表示不打乱。 - 每组用例第一行 $n, s$，随后 $n-1$ 行每行 $u, v$，表示一条树边。 - `program` ：你的已编译程序文件名。 - `arguments` ：为你的程序所需参数。 工具命令最上方有详细说明。 **注意事项**： - 工具并非与评测机完全一致，判罚可能略有不同。 - 工具会检查文件格式，但不会校验输入是否满足题目限制。 - 工具不会检测你的时间/空间消耗限制。 --- （注：题目描述中的所有 LaTeX 数学公式、代码及格式已完整保留，未做更改。） 由 ChatGPT 5 翻译