题目背景

译自 NOISG 2018 Finals D. City Mapping。

---

当你在洛谷提交本题时，需要注意：

• 本题仅支持 C++ 系列语言。
• 你的代码中不应该包含头文件 citymapping.h。
• 你的代码中应当有如下两行函数声明：

  long long get_distance(int X, int Y);
  void find_roads(int N, int Q, int A[], int B[], int W[]);
  

如遇评测问题，请联系搬题人。

题目描述

这是一道交互题。

Silvermill 市是一座有 $N$ 个路口和 $N-1$ 条道路的城市。其中道路的编号为 $0$ 到 $N-2$。

第 $i$ 条道路双向连接了 $(A_i,B_i)$ 两个路口，从任意方向通过这条道路都需要花费 $W_i$ 分钟。保证任意两个路口之间都能通过道路互相到达。

为了避免交通堵塞，Silvermill 市的每个路口连接的道路不会超过 $3$ 条。

你的任务是画出 Silvermill 市的地图，也就是找出所有 $N-1$ 条道路的 $(A_i,B_i,W_i)$。

为了达到这个目的，你可以询问市长至多 $Q$ 次从任意一个路口 $X$ 到任意一个路口 $Y$ 最少需要多少分钟。

实现细节

在本题中，你不需要，也不应该实现主函数。

你需要实现如下函数：

void find_roads(int N, int Q, int A[], int B[], int W[])

该函数包含两个输入参数和三个输出参数，将在评测时被运行恰好一次。输入参数为 $N,Q$，分别表示路口的数量和最大询问次数；输出参数为 $A,B,W$，你需要确定城市中的 $N-1$ 条道路，按题意中的含义以数组 $A,B,W$ 的形式返回。返回道路的顺序可以是任意的，同一道路端点的顺序也可以是任意的。

注意数组的下标是从 $0$ 开始的。

你可以调用下面的函数来完成任务：

long long get_distance(int X, int Y)

该函数将返回一个整数，表示从路口 $X$ 到路口 $Y$ 最少需要多少分钟。如果你调用此函数超过 $Q$ 次，或提供无效的路口编号作为参数，程序将立刻终止，你将得到 Wrong Answer 的评测状态。

输入格式

示例测试程序如下方式读入数据：

第一行三个整数 $N,Q,S$，分别表示路口的数量、最大询问次数和子任务编号。

之后是 $N-1$ 行，每行三个整数 $(A_i,B_i,W_i)$，描述一条道路。

输出格式

示例测试程序可能会产生的输出如下：

• Wrong Input Format，意味着对示例测试程序的输入格式有误。
• Wrong Answer: Reported list of edges differ from actual.，意味着你确定的道路与实际情况不符。
• Wrong Answer: get_distance() arguments out of range.，意味着你在询问时提供了无效的路口编号作为参数。
• Wrong Answer: Too many calls to get_distance().，意味着你超出了最大询问次数限制。
• 包含两行信息，分别是 Score: s% 和 Correct: x out of y queries used.，意味着你获得了该测试点 $s\%$ 的分数，最大询问次数为 $y$ 次，你使用了其中的 $x$ 次。

提示

调用示例

我们考虑如下的城市地图，展示一种可能的函数调用过程。

假设此时最大询问次数 $Q=5\times 10^5$。

你的函数将这样被调用恰好一次：

find_roads(5, 500000, A, B, W);

其中 $A,B,W$ 是定义在测试程序中的数组。

一种可能的交互过程如下：

• get_distance(5, 4) = 10：get_distance 函数返回从路口 $5$ 到达路口 $4$ 的最少分钟数。路线 $5\to 3\to 4$ 是最短的，需要 $10$ 分钟。
• get_distance(2, 4) = 1：get_distance 函数返回了从路口 $2$ 到达路口 $4$ 的最少分钟数。直接从 $2$ 走到 $4$ 是最短的，需要 $1$ 分钟。
• get_distance(1, 3) = 15：get_distance 函数返回了从路口 $1$ 到达路口 $3$ 的最少分钟数。路线 $1\to 4\to 3$ 是最短的，需要 $15$ 分钟。
• get_distance(1, 2) = 9：get_distance 函数返回了从路口 $1$ 到达路口 $2$ 的最少分钟数。路线 $1\to 4\to 2$ 是最短的，需要 $9$ 分钟。

此时，我们假设你的 find_roads 函数认为自己已经掌握了足够的信息，可以推导出正确的地图，所以将 $A,B,W$ 数组分别赋值为 $A=[3,4,4,5],B=[4,1,2,3],W=[7,8,1,3]$，然后终止。

这只是一种可能的答案，因为返回道路的顺序可以是任意的，同一道路端点的顺序也可以是任意的。

子任务

对于 $100\%$ 的数据，$2\le N\le1000$，$1\le A_i,B_i\le N$，$1\le W_i\le 10^9$。

子任务	得分	$Q$	特殊性质及备注
$1$	$9$	$=5\times 10^5$	$W_i=1$
$2$	$16$		无特殊限制
$3$	$13$	$=12000$	每个路口最多连接两条道路，且 $W_i=1$
$4$	$19$		每个路口最多连接两条道路
$5$	$43$	$=25000$	无特殊限制，但有特殊的计分规则（请参阅计分细则）

计分细则

子任务 $5$ 适用于以下的计分规则。你的得分依赖于你实现的函数询问的次数 $q$。

• 如果 $q>25000$，你将获得 $0$ 分。
• 如果 $12000<q\le 25000$，你将获得 $10-10\times \frac{q-12000}{13000}$ 分。
• 如果 $6500<q\le 12000$，你将获得 $40-30\times \frac{q-6500}{5500}$ 分。
• 如果 $q\le 6500$，你将获得 $43$ 分。

本地测试方式

我们在附件中下发了示例测试程序 grader.cpp，头文件 citymapping.h，你所需完成的代码的示例 citymapping.cpp，以及编译文件 compile.sh。

将这些文件置于同一文件夹下，使用 compile.sh 编译并运行生成的可执行文件，即可进行本地测试。

下发的示例测试程序与提交后使用的测试程序有所不同。

注意提交到洛谷上时有特殊的要求。