• 比赛：EJOI 2026 Day 1
• 时间限制：4 秒
• 内存限制：1024 MiB
• 题目类型：交互题

题目描述

地图上有 $N$ 个地点和 $N$ 支队伍。每支队伍都必须访问全部地点，并且起点互不相同：队伍 $i$ 从地点 $i$ 出发。

比赛组织者秘密选出了 $N-1$ 条快速公共交通线路。每条线路连接两个地点，并保证任意地点都可以通过这些线路到达任意其他地点。因此这些线路构成一棵树。

随后，对于每一个起点 $i$，组织者在这棵树上生成了一种任意的 DFS（深度优先搜索）首次访问顺序，并把该顺序作为队伍 $i$ 的路线。

不同起点的 DFS 可以使用不同的邻接点访问顺序。

Bissy 想恢复组织者隐藏的整棵树。

她只能询问：

“队伍 $i$ 的路线中，第 $j$ 个地点是什么？”

请实现程序，恢复这棵隐藏树。

DFS 首次访问序

从指定顶点 $v$ 开始进行深度优先搜索。每次递归进入一个尚未访问的邻点；若不存在这样的邻点，则回退到前一个顶点继续。

DFS walk 指各顶点第一次被访问时的顺序。

例如，同一棵树从顶点 4 出发，根据邻接点选择顺序不同，可能得到：

[4,1,2,0,3,6,7,5]

也可能得到：

[4,3,5,7,6,1,0,2]。

隐藏树以及全部 $N$ 个 DFS 序列都在程序开始前固定，不会因你的询问发生变化。

实现要求

实现：

std::vector<std::pair<int,int>> find_tree(int N);

• N：地点数；
• 返回值：长度为 $N-1$ 的边列表。

边的顺序以及每条边两个端点的顺序均任意。

每个测试中，该函数最多调用 $T$ 次。

交互函数

int guess(int i, int j);

它返回从地点 $i$ 出发的 DFS walk 中第 $j$ 个地点。

特别地：

guess(i,0) 一定返回 $i$。

必须满足 $0\le i,j\le N-1$，否则会得到 Output isn't correct: Invalid call。

在子任务 0～6 中，一次 guess 可视作 $O(1)$；在子任务 7 中一次调用耗时 $O(\log N)$。

数据范围

• $2\le N\le2^{16}+1$。

令一次测试中所有 find_tree 调用的最大 $N$ 为 $N_{\max}$：

• 若 $N_{\max}\le9$，则 $1\le T\le100$；
• 若 $N_{\max}\le2^{10}+1$，则 $1\le T\le10$；
• 若 $N_{\max}\le2^{16}+1$，则 $1\le T\le3$。

系统 grader 自身最多使用 280 MiB 内存，这部分也计入总内存限制。

交互样例

假设隐藏树有 6 个顶点，并且从地点 0 出发的 DFS walk 为：

[0,1,2,4,3,5]。

一种可能的交互为：

Jury:        find_tree(6)

Participant: guess(0,0)
Jury:        0
Participant: guess(0,1)
Jury:        1
Participant: guess(0,2)
Jury:        2
Participant: guess(0,3)
Jury:        4
Participant: guess(0,4)
Jury:        3
Participant: guess(0,5)
Jury:        5

Participant: return {{0,1},{0,2},{4,0},{5,4},{3,4}}

原题指出：上述询问信息本身并不足以唯一确定一棵树，但在子任务 0 的示例测试中，这正是正确答案。

子任务

子任务	分值	$N$	额外限制
0		-	样例
1	11	$\le9$	无
2	6	$\le100$	每个顶点的度数至多为 2
3	13		每次 DFS 都优先向“离顶点 0 更远”的方向走；若存在多个选择则任选
4	11		除顶点 0 外，其余顶点的度数至多为 2
5	10		无
6	31	$\le2^{10}+1$
7	18	$\le2^{16}+1$

计分方式

子任务 0～5：只要在限制内正确恢复树，就获得该子任务全部分数。

对子任务 6、7，得分比例 $S$ 取决于该测试中某个子测试所使用的最大询问次数 $Q_{\max}$：

• 若 $Q_{\max}\le L_1$，则 $S=1$；
• 若 $L_1<Q_{\max}\le L_2$，则
  $S=0.4+0.6\cdot\frac{L_2-Q_{\max}}{L_2-L_1}$；
• 若 $L_2<Q_{\max}\le3L_2$，则
  $S=0.2+0.2\cdot\frac{3L_2-Q_{\max}}{2L_2}$；
• 若 $Q_{\max}>3L_2$，则 $S=0.2$。

其中：

• 子任务 6：$L_1=3(2^{10}+1)=3075$，$L_2=9(2^{10}+1)=9225$；
• 子任务 7：$L_1=3(2^{16}+1)=196611$，$L_2=15(2^{16}+1)=983055$。

整个子任务最终获得的比例，是所有测试中 $S$ 的最小值。

Sample grader

官方提供两个 grader。

本地测试：Lgrader.cpp

与参赛程序一起编译。

输入：

1. 测试数 $T$；
2. 对每个测试：
   • 一个整数 $N$；
   • 接下来 $N-1$ 行为树边；
   • 再接下来 $N$ 行，每行 $N$ 个整数，为各起点的 DFS walk，并要求第 $i$ 行必须从顶点 $i$ 开始。

可以把 grader 中的 AUTO_GENERATE 设为 true，让 grader 自动生成 DFS walk。

输出为错误信息，或每个测试使用的询问次数及全局最大询问次数。

该 grader 不适合子任务 7 的超大规模。

系统用户测试：stub.cpp

可用于系统中的 user tests，输入格式与上述 grader 相同，但不提供自动生成 walk 的功能。