P10440 [JOIST 2024] 环岛旅行 / Island Hopping

**由于部分 BUG，使用 C++14 (GCC9) 提交会产生编译错误，请使用 C++14 等语言进行提交。** **题目译自 [JOISC 2024](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html) Day4 T2 「[島巡り](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/contest4/island.pdf) / [Island Hopping](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/contest4/island-en.pdf)」**。翻译来源 LOJ。 **不要引入 `island.h`**。你应该在文件头添加以下声明： ``` int query(int, int); void answer(int, int); ``` 交互文件可在 [JOI 官网](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html)下载。

**这是一道交互题。本题交互库是非自适应的。** JOI 国有 $N$ 座岛屿，编号为 $1$ 到 $N$。有 $N-1$ 条航线，编号为 $1$ 到 $N-1$。航线 $j\ (1\le j\le N-1)$ 双向连接岛屿 $A_j$ 和 $B_j$。可以从一座岛屿出发，通过一些航线到达任意另一个岛屿。 葵准备在 JOI 国旅行。然而她不知道 JOI 国的航线。她准备向 JOI 国居住的 Bitaro 按下面的方式提一些问题： 1. 葵告诉 Bitaro 两个整数 $v$ 和 $k$，其中 $1\le v\le N,1\le k\le N-1$。 2. Bitaro 会告诉她除了 $v$ 之外的其他 $N-1$ 座岛屿中，距离 $v$ 第 $k$ 近的岛屿编号。更确切地说，他会告诉她一个整数 $i$，满足 $\text{dist}(v,i)\times N+i\ (1\le i\le N,i\neq v)$ 是第 $k$ 小的，其中 $\text{dist}(v,i)$ 是从岛屿 $v$ 到 $i$ 所经过的最小航线数。 葵想通过提问知道所有 JOI 国的航线。因为葵不想花费太多时间，所以她最多只能向 Bitaro 问 $L$ 个问题。 给定 JOI 国的岛屿数和提问限制数，写一个程序模拟葵的提问策略，以找出所有的航线。 ### 实现细节 你需要在程序开头引入库 `island.h`。 你需要实现如下函数。 - `void solve(int N, int L)` 此函数在每个测试点中只被调用一次 - 参数 `N` 是岛屿数 $N$ - 参数 `L` 是提问次数限制 $L$。 在程序中，你可以调用如下函数。 - `int query(int v, int k)` 葵使用此函数向 Bitaro 提问 - 参数 `v` 必须在 $1$ 到 $N$ 之间。如果不是，你的程序会被判为 **Wrong Answer [1]**。 - 参数 `k` 必须在 $1$ 到 $N-1$​ 之间。如果不是，你的程序会被判为 **Wrong Answer [2]**。 - 返回值表示除 $v$ 之外的其他 $N-1$ 个岛屿中，距离 $v$ 第 $k$ 近的岛屿编号。参考题目描述获得更详细的定义。 - 你不能调用 `query` 函数超过 $L$ 次，否则你的程序会被判为 **Wrong Answer [3]**。 - `void answer(int x, int y)` 使用此函数回答 JOI 国的一条航线 - 参数 `x` 和 `y` 表示被一条航线连接的两座岛屿。 - 参数 `x` 和 `y` 必须在 $1$ 到 $N$ 之间。如果不是，你的程序会被判为 **Wrong Answer [4]**。 - 必须存在一条连接岛屿 `x` 和 `y` 的航线。换句话说，必须存在一个整数 $j\ (1\le j\le N-1)$ 满足 $x=A_j,y=B_j$ 或 $x=B_j,y=A_j$。否则，你的程序会被判为 **Wrong Answer [5]**。 - 你的程序不能回答相同的航线两次或以上。否则，你的程序会被判为 **Wrong Answer [6]**。 - 函数 `answer` 必须被调用恰好 $N-1$ 次。如果 `solve` 函数运行结束后此函数调用次数不是 $N-1$，你的程序会被判为 **Wrong Answer [7]**。 ### 注意事项 - 你的程序可以实现其它函数供内部使用，或者使用全局变量。 - 你的程序禁止使用标准输入输出。你的程序禁止与其他文件通过任何方式交互。然而，你的程序可以使用标准错误输出输出调试信息。 - 测评中使用的交互器**不是**自适应性的。这意味着每组测试点的答案是提前确定好的。 ### 编译运行 你可以在附件中下载样例交互器来测试你的程序。附加文件中还包含一个样例程序。 样例交互器是文件 `grader.cpp`。为了测试你的程序，请将 `grader.cpp`，`island.cpp` 和 `island.h` 放在同一目录下，并且执行如下命令编译程序。此外你也可以运行 `compile.sh` 来编译你的程序。 ```bash g++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp ``` 当编译成功时，会生成可执行文件 `grader`。 注意测评时使用的交互器与样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入数据，输出结果到标准输出。

Sample Grader 输入格式如下： 第一行两个整数 $N,L$。 接下来 $N-1$ 行，每行两个整数 $A_j,B_j$。

样例交互器将向标准输出中输出如下信息： - 如果你的程序被判为正确，它会报告调用 `query` 的次数，如：`Accepted: 2024`。 - 如果你的程序被判为某种 Wrong Answer，样例交互程序会输出它的类别，如：`Wrong Answer [4]`。 如果你的程序满足多种 Wrong Answer 的类别，样例交互器只会报告其中一个。

### 样例交互 #### 样例交互 $1$ 样例调用过程如下表所示。 | 调用 | 调用 | 返回值 | | :------------: | :------------: | :----: | | `solve(4, 16)` | | | | | `query(2, 1)` | $1$ | | | `query(3, 1)` | $4$ | | | `answer(2, 4)` | | | | `query(2, 2)` | $4$ | | | `answer(2, 1)` | | | | `query(3, 2)` | $2$ | | | `query(2, 1)` | $1$ | | | `answer(3, 4)` | | 从岛屿 $2$ 到岛屿 $1,3,4$ 的最小经过航线数分别为 $1,2,1$。例如，从岛屿 $2$ 到岛屿 $3$，我们可以使用航线 $2$ 后使用航线 $3$。 将岛屿按 $\text{dist}(2,i)\times N+i\ (i\neq 2)$ 递增的顺序排序，结果是岛屿 $1,4,3$。因此，`query(2, 1)` 的返回值为 $1$，`query(2, 2)` 的返回值为 $4$。 样例 $1$ 满足子任务 $2,6$ 的限制。 #### 样例交互 $2$ 样例调用过程如下表所示。 | 调用 | 调用 | 返回值 | | :------------: | :------------: | :----: | | `solve(5, 25)` | | | | | `query(1, 3)` | $5$ | | | `query(1, 4)` | $2$ | | | `answer(3, 1)` | | | | `query(2, 4)` | $4$ | | | `query(3, 1)` | $1$ | | | `query(3, 2)` | $4$ | | | `answer(1, 5)` | | | | `answer(4, 1)` | | | | `answer(2, 5)` | | 从岛屿 $1$ 到岛屿 $2,3,4,5$ 的最小经过航线数分别为 $2,1,1,1$。例如，从岛屿 $1$ 到岛屿 $2$，我们可以使用航线 $4$ 后使用航线 $1$。 将岛屿按 $\text{dist}(1,i)\times N+i\ (i\neq 1)$ 递增的顺序排序，结果是岛屿 $3,4,5,2$。因此，`query(1, 3)` 的返回值为 $5$，`query(1, 4)` 的返回值为 $2$。 样例 $2$ 满足子任务 $4,6$ 的限制。 ### 数据范围 - $3\le N\le 300$ - $1\le A_j,B_j\le N\ (1\le j\le N-1)$ - $A_j\neq B_j\ (1\le j\le N-1)$ - 可以通过航线，从一个岛屿到达任意其他岛屿 ### 子任务 | 子任务 | 附加限制 | 分值 | | :----: | :----------------------------------------------------------: | :--: | | $1$ | $N=3,L=9$ | $2$ | | $2$ | $L=N^2$，每座岛屿最多有两条航线连接 | $4$ | | $3$ | $L=2N$，每座岛屿最多有两条航线连接 | $7$ | | $4$ | $L=N^2$，岛屿 $1$ 有三条航线连接，其他每座岛屿最多有两条航线连接 | $9$ | | $5$ | $L=3N$，岛屿 $1$ 有三条航线连接，其他每座岛屿最多有两条航线连接 | $13$ | | $6$ | $L=N^2$ | $15$ | | $7$ | $L=3N$ | $22$ | | $8$ | $L=2N$ | $28$ |