#P16893. [EJOI 2026]Reconstruct

[EJOI 2026]Reconstruct

树的重建

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

题目描述

地图上有 NN 个地点和 NN 支队伍。每支队伍都必须访问全部地点,并且起点互不相同:队伍 ii 从地点 ii 出发。

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

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

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

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

她只能询问:

“队伍 ii 的路线中,第 jj 个地点是什么?”

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

DFS 首次访问序

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

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

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

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

也可能得到:

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

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

实现要求

在程序开头包含 #include "reconstruct.h",不编写 main,实现:

std::vector<std::pair<int,int>> find_tree(int N);
  • N:地点数;
  • 返回值:长度为 N−1N-1 的边列表。

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

每个测试中,该函数最多调用 TT 次。

交互函数

int guess(int i, int j);

它返回从地点 ii 出发的 DFS walk 中第 jj 个地点。

特别地:

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

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

在子任务 0~6 中,一次 guess 可视作 O(1)O(1);在子任务 7 中一次调用耗时 O(log⁡N)O(\log N)。

数据范围

  • 2≤N≤216+12\le N\le2^{16}+1。

令一次测试中所有 find_tree 调用的最大 NN 为 Nmax⁡N_{\max}:

  • 若 Nmax⁡≤9N_{\max}\le9,则 1≤T≤1001\le T\le100;
  • 若 Nmax⁡≤210+1N_{\max}\le2^{10}+1,则 1≤T≤101\le T\le10;
  • 若 Nmax⁡≤216+1N_{\max}\le2^{16}+1,则 1≤T≤31\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 的示例测试中,这正是正确答案。

子任务

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

计分方式

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

对子任务 6、7,得分比例 SS 取决于该测试中某个子测试所使用的最大询问次数 Qmax⁡Q_{\max}:

  • 若 Qmax⁡≤L1Q_{\max}\le L_1,则 S=1S=1;
  • 若 L1<Qmax⁡≤L2L_1<Q_{\max}\le L_2,则
    S=0.4+0.6⋅L2−Qmax⁡L2−L1S=0.4+0.6\cdot\frac{L_2-Q_{\max}}{L_2-L_1};
  • 若 L2<Qmax⁡≤3L2L_2<Q_{\max}\le3L_2,则
    S=0.2+0.2⋅3L2−Qmax⁡2L2S=0.2+0.2\cdot\frac{3L_2-Q_{\max}}{2L_2};
  • 若 Qmax⁡>3L2Q_{\max}>3L_2,则 S=0.2S=0.2。

其中:

  • 子任务 6:L1=3(210+1)=3075L_1=3(2^{10}+1)=3075,L2=9(210+1)=9225L_2=9(2^{10}+1)=9225;
  • 子任务 7:L1=3(216+1)=196611L_1=3(2^{16}+1)=196611,L2=15(216+1)=983055L_2=15(2^{16}+1)=983055。

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

Hydro 批量调用

本地库额外提供等价的批量接口,用于减少进程间传输的往返次数:

std::vector<int> guess_batch(
    const std::vector<std::pair<int,int>>& queries);

返回值依次对应每个 (i,j) 的 guess(i,j) 结果。一批包含多少个查询,就累计多少次询问,重复查询也分别计数;询问范围和全部评分阈值不变。原 guess 接口仍可单独使用。批量接口适合同时已知、彼此不依赖的查询,不提供额外信息。

本地测试文件

下载 reconstruct.h、sample_grader.cpp 和 sample.in,与自己的 solution.cpp 放在同一目录。

g++ -std=c++17 -O2 solution.cpp sample_grader.cpp -o sample
./sample < sample.in

本地样例器的输入为:第一行测试数 TT;每组先给 NN,再给 N−1N-1 条无向边,顶点编号为 00 到 N−1N-1。样例器为每个起点独立生成并固定一个合法 DFS 首次访问序,调用你的 find_tree,核对返回的边并显示询问次数。

该样例器仅用于 N≤1025N\le1025 的本地测试。正式评测覆盖题面中的全部规模。正式库只通过询问接口提供信息,不向选手函数提供隐藏树或其他起点的完整路线;请勿向标准输入输出读写任何数据。