P17271 [eJOI 2026] Reconstruct
题目描述
*这是一道交互题。*
Bissy 即将参加由志愿者组织的定向游戏 *Final destination*，EJOI 的各支代表队会在其中竞相访问城市里的不同地点。相比获胜，Bissy 对游戏的设计方式更感兴趣。
地图上有 $N$ 个地点和 $N$ 支队伍。每支队伍都要访问所有地点，并且起始地点各不相同：队伍 $i$ 从地点 $i$ 出发。每支队伍都有自己的路线。
这些路线基于一个由快速公共交通线路组成的隐藏结构。评测方选择了 $N-1$ 条线路，每条线路连接一对地点，并保证任意地点都能通过这些线路到达其他任意地点。这样的结构是一棵树。随后，对于每个起始地点 $i$，评测方生成了一次任意的 DFS 遍历，并将其作为队伍 $i$ 的路线。
Bissy 想找出隐藏的公共交通树。她可以询问：
> 队伍 $i$ 的第 $j$ 个目的地是什么？
请编写 `find_tree` 找出隐藏树。
树的一次 **DFS 遍历**是深度优先搜索中各顶点第一次被访问的顺序。搜索从给定顶点 $v$ 开始，递归前往某个尚未访问的相邻顶点；当不存在这样的顶点时，退回此前访问的顶点并继续。
:::align{center}
:::
图中 $v=4$，边上的箭头表示深度优先搜索的步骤，生成的遍历为 $[4,1,2,0,3,6,7,5]$。访问相邻顶点的顺序会影响结果；另一次可能的遍历为 $[4,3,5,7,6,1,0,2]$。
树和全部 $N$ 次 DFS 遍历在程序开始前已经固定，不会根据你的询问发生改变。不同遍历使用的相邻顶点顺序可以不同。
### 实现细节
你需要实现：
```cpp
std::vector find_tree(int N)
```
- $N$：地点数；
- 返回值：由 $N-1$ 条树边组成的列表，边的顺序以及每条边两个端点的顺序均不限。
在每个测试中，该函数最多调用 $T$ 次。
你可以调用以下函数与评测器交互：
```cpp
int guess(int i, int j)
```
它返回从地点 $i$ 出发的 DFS 遍历中第 $j$ 个地点。特别地，`guess(i, 0)` 会返回 $i$。在子任务 $0$ 至 $6$ 中，该函数会在 $O(1)$ 时间内返回；在子任务 $7$ 中，会在 $O(\log N)$ 时间内返回。必须满足 $0\le i,j\le N-1$，否则程序会得到 `Output isn't correct: Invalid call`。
输入格式
题目提供了两个样例评测器。
本地测试时，可将 `Lgrader.cpp` 与你的程序一起编译。程序先读入测试用例数 $T$。对于每个测试用例，先读入 $N$，再读入 $N-1$ 行树边，最后读入 $N$ 行、每行 $N$ 个整数，表示各次 DFS 遍历。第 $i$ 次遍历必须从顶点 $i$ 开始。将常量 `AUTO_GENERATE` 设为 `true`，可让评测器自动生成遍历。若结果错误，评测器会报告错误；否则会输出每个测试用例的询问次数及全局最大值。该评测器不支持足够大的 $N$，具体而言不支持子任务 $7$ 的限制。
系统用户测试可使用 `stub.cpp` 与你的程序一起编译。输入格式相同，但不提供自动生成遍历的功能。
输出格式
无
说明/提示
### 样例
假设隐藏的公共交通树如下：
假设从地点 $0$ 出发的遍历为 $[0,1,2,4,3,5]$。一次可能的交互如下：
| 选手程序 | 评测程序 |
|---|---|
| | `find_tree(6)` |
| `guess(0, 0)` | 返回 `0` |
| `guess(0, 1)` | 返回 `1` |
| `guess(0, 2)` | 返回 `2` |
| `guess(0, 3)` | 返回 `4` |
| `guess(0, 4)` | 返回 `3` |
| `guess(0, 5)` | 返回 `5` |
| `return {{0,1},{0,2},{4,0},{5,4},{3,4}};` | |
这些询问提供的信息不足以唯一确定树，但这确实是子任务 $0$ 中该测试的答案。
### 限制
- $2\le N\le 2^{16}+1$
- 令 $N_{\max}$ 为同一测试内所有调用中 $N$ 的最大值：
- 若 $N_{\max}\le 9$，则 $1\le T\le 100$；
- 若 $N_{\max}\le 2^{10}+1$，则 $1\le T\le 10$；
- 若 $N_{\max}\le 2^{16}+1$，则 $1\le T\le 3$。
- 系统评测器最多可使用 280 MiB 内存，这部分内存计入你的程序内存限制。
### 子任务
| 子任务 | 分值 | $N$ | 附加限制 |
|:--:|:--:|:--:|---|
| 0 | 0 | - | 样例。 |
| 1 | 11 | $\le 9$ | - |
| 2 | 6 | $\le 100$ | 每个顶点最多与另外两个顶点相连。 |
| 3 | 13 | $\le 100$ | 每次遍历都由 DFS 生成，并在每一步优先远离顶点 $0$；若有多个远离方向可选，则任意选择一个。 |
| 4 | 11 | $\le 100$ | 除顶点 $0$ 外，每个顶点最多与另外两个顶点相连。 |
| 5 | 10 | $\le 100$ | - |
| 6 | 31 | $\le 2^{10}+1$ | - |
| 7 | 18 | $\le 2^{16}+1$ | - |
### 评分
对于子任务 $0$ 至 $5$，只要在时间限制内成功找出树即可获得满分。对于子任务 $6$ 和 $7$，令 $Q_{\max}$ 为某个测试中单个子测试使用的最大询问次数。该测试的得分比例 $S$ 为：
- 若 $Q_{\max}\le L_1$，则 $S=1.0$；
- 若 $L_1