P13346 [EGOI 2025] Laser Strike / 激光突击
题目背景
请选择 C++20 提交。
题目描述
Ann 和她的朋友 Kathrin 最近发现了一款新桌游，这款游戏成了她们的最爱：Laser Strike。在这款游戏中，两位玩家需要协作将棋盘上的 $N$ 个棋子全部移除。游戏分为两个阶段。关键在于，Kathrin 并不了解全部信息。为了赢得游戏，Ann 和 Kathrin 必须协作，并且尽量减少交流。
棋盘上有 $N$ 个独特的棋子，编号为 $0$ 到 $N-1$。两位玩家都可以看到这些棋子。此外，棋盘上有 $N-1$ 条连接，每条连接连接一对棋子，使得任意两个棋子之间都可以通过若干条连接到达。换句话说，这些连接构成了一棵树。**只有 Ann 能看到这些连接；Kathrin 并不知道它们。**
在游戏的第一阶段，Ann 决定一个移除棋子的顺序 $l_0, l_1, \ldots, l_{N-2}$，直到只剩下最后一个棋子。这个顺序对 Kathrin 保密。如果 Kathrin 能复现这个顺序，两人就能赢得游戏。每次移除棋子时，需满足如下规则：每次被移除的棋子，必须与仅剩的一个棋子直接连接。换句话说，每次被移除的棋子都必须是当前剩余树中的一个叶子节点。（当 $N-1$ 个棋子都被移除后，最后一个棋子自动被移除，游戏胜利。）Ann 必须选择一个满足上述规则的移除顺序。
Ann 还会写下一条信息给 Kathrin，形式为一个二进制字符串。Ann 可以自选信息长度——信息越短，得分越高。
之后，游戏进入第二阶段。目标是让 Kathrin 按顺序 $l_0, l_1, \ldots, l_{N-2}$ 移除 $N-1$ 个棋子。她会进行 $N-1$ 步操作。在第 $i$ 步操作前，Ann 会告诉 Kathrin 一对整数 $a, b$，满足：
* $a < b$；
* 这两个棋子 $a$ 和 $b$ 之间在当前剩余棋子中有直接连接；
* $a$ 或 $b$ 中有一个就是本轮应被移除的棋子 $l_i$。
注意，对于 Ann 来说，当前树中每个叶子 $l_i$ 都能唯一确定一个连接 $(a, b)$。
然后，Kathrin 会选择移除 $a$ 或 $b$ 中的一个棋子。如果她移除的是正确的叶子 $l_i$，游戏继续；否则游戏失败。
你的任务是同时实现 Ann 和 Kathrin 的策略，使她们能够赢得游戏。
你的程序得分取决于 Ann 在第一阶段写下的信息长度。
### 实现细节
**这是一道通信题。**
本题为多轮运行题目，你的程序会被执行两次。第一次运行时，实现 Ann 的策略（第一阶段）；第二次运行时，实现 Kathrin 的策略（第二阶段）。
输入的第一行包含两个整数 $P$ 和 $N$，其中 $P$ 为 1 或 2（分别表示第一或第二阶段），$N$ 为棋子数量。
后续输入内容取决于阶段：
**阶段 1：Ann**
第一行后，接下来 $N-1$ 行描述树的结构。每行两个整数 $a$ 和 $b$（$0 \leq a < b \leq N-1$），表示棋子 $a$ 和 $b$ 之间有一条连接。
你的程序应首先输出一个二进制字符串（长度不超过 1000），即 Ann 写给 Kathrin 的信息。若信息长度为 0，输出空行。
然后输出 $N-1$ 个整数 $\ell_0, \ell_1, \ldots, \ell_{N-2}$，每行一个，表示 Ann 希望的叶子移除顺序。该顺序必须满足每次移除的都是当前树的叶子。
**阶段 2：Kathrin**
第一行后，下一行输入为 Ann 的二进制信息。
接下来有 $N-1$ 轮交互，每轮代表 Kathrin 的一次操作。
在第 $i$ 轮，你的程序应首先读入两个整数 $a$ 和 $b$（$0 \leq a < b \leq N-1$）。其中一个是当前应移除的叶子 $\ell_i$，另一个是唯一与其直接连接的剩余棋子。然后，你的程序应输出 $\ell_i$，即 Kathrin 选择移除该叶子。如果输出不是正确的叶子，游戏失败，本测试点判为 Wrong Answer。
### 细节说明
两次运行的总时间不得超过时限，否则会被判为 TLE。
每次输出后请及时刷新标准输出，否则可能被判为 TLE。Python 用 `input()` 读入时自动刷新；C++ 可用 `cout
输入格式
见实现细节。
输出格式
见实现细节。
说明/提示
### 样例说明
注意，以下样例 $N=7$，仅为说明方便，并非正式测试用例。正式评测所有用例均有 $N=1000$。
在样例中，Ann 得到如下树结构。在第一阶段，Ann 读入树，选择二进制串 "0110" 发送给 Kathrin，并选择移除顺序 $[\ell_0, \ell_1, \ldots, \ell_{N-2}] = [5, 3, 2, 6, 4, 0]$。第二阶段，Kathrin 收到 Ann 的二进制串 "0110"，随后收到对 $(1,5)$ 并选择移除 5，接着收到对 $(2,3)$ 并移除 3，依此类推。下图展示了交互过程：
### 测试工具
为方便测试，官方提供了一个简单的工具。见 Kattis 题目页面底部的“attachments”。该工具可选，正式评测器与该工具不同。
用法：准备一个输入文件（如 "sample1.in"），文件第一行为 $N$，接下来 $N-1$ 行描述树结构，格式同阶段 1。例如：
```
7
0 1
1 2
2 3
0 4
0 6
1 5
```
对于 Python 程序（如 solution.py，通常用 `pypy3 solution.py` 运行），可用如下命令：
```
python3 testing_tool.py pypy3 solution.py < sample1.in
```
C++ 程序编译后（如 `g++ -g -O2 -std=gnu++23 -static solution.cpp -o solution.out`），可用如下命令：
```
python3 testing_tool.py ./solution.out < sample1.in
```
### 约束与评分
* $N = 1000$
* 对所有连接，$0 \leq a < b \leq N-1$
你的解答将在一组测试组上进行评测，每组包含若干测试用例。要获得该测试组分数，你需要通过该组所有测试用例。
| 组别 | 满分 | 限制 |
| :-: | :-: | :-: |
| 1 | 8 | 树为星形，即除一个节点外其余全为叶子 |
| 2 | 9 | 树为链形，即除两个叶子外其余每个节点度数为 2 |
| 3 | 21 | 树为“星形加链”，即所有节点度为 1 或 2，只有一个节点度大于 2 |
| 4 | 36 | 任意两点间距离不超过 10 |
| 5 | 26 | 无额外限制 |
对于每个通过的测试组，你的得分按下式计算：
$$\text{score} = S_g \cdot (1 - 0.3 \cdot \log_{10} \max(K, 1))$$
其中 $S_g$ 为该测试组满分，$K$ 为该组任一测试用例中 Ann 的消息最大长度。每组得分四舍五入取整。
下表给出若干 $K$ 时的总分示例，若所有测试组都通过且 $K$ 如下：
| $K$ | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 得分 | 100 | 79 | 70 | 49 | 39 | 20 | 11 |
翻译由 ChatGPT-4.1 完成。