CityMapping（城市测绘）

本题为 函数式交互题（Grader 题）。提交的程序不从标准输入读取数据，也不向标准输出输出答案；你只需要实现指定函数。

题目描述

Peanut 准备前往 Silvermill 城度假，因此需要得到这座城市的地图。

Silvermill 有 $N$ 个道路交叉口，编号为 $1,2,\ldots,N$，以及恰好 $N-1$ 条双向道路。第 $i$ 条道路连接交叉口 $A_i$ 与 $B_i$，通过它需要 $W_i$ 分钟。

城市保证连通，因此这些道路构成一棵带正边权的树。为了避免拥堵，每个交叉口连接的道路数不超过 $3$。

Peanut 需要恢复整张城市地图，也就是确定全部 $N-1$ 条道路的两个端点及其边权。

他雇用了一名制图师。制图师只能回答如下询问：

• 从交叉口 $X$ 到交叉口 $Y$ 的最短旅行时间是多少？

制图师最多回答 $Q$ 次询问。你需要在询问次数限制内恢复整棵树。

实现要求

你需要提交一个 C++ 源文件，并实现下列函数：

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

评测程序会恰好调用该函数一次。

参数说明

• N：道路交叉口数量；
• Q：最多允许调用 get_distance 的次数；
• A、B、W：长度均至少为 $N-1$ 的输出数组。

函数结束前，你需要填写：

(A[i], B[i], W[i])，0 <= i < N-1

使其恰好描述城市中的全部 $N-1$ 条道路。

道路顺序可以任意，每条道路的两个端点顺序也可以任意。例如，道路 $(2,5,7)$ 可以写成 $(5,2,7)$。

可调用函数

你可以调用评测程序提供的函数：

long long get_distance(int X, int Y);

该函数返回从交叉口 $X$ 到交叉口 $Y$ 的最短旅行时间。

注意：

• $1\le X,Y\le N$；
• 可以询问同一个交叉口，此时返回 $0$；
• 总调用次数不能超过 $Q$；
• 若参数越界或调用次数超过 $Q$，该测试点立即判为错误。

提交格式

你的代码需要包含：

#include "citymapping.h"

并实现 find_roads。不要编写 main 函数。

一个最小模板如下：

#include "citymapping.h"

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    // 在这里实现你的算法。
}

本题在该 Hydro OJ 配置中仅支持 C++ 提交。

示例说明

下图是一座有 $5$ 个交叉口和 $4$ 条道路的城市：

其道路为：

• $1\leftrightarrow4$，边权为 $8$；
• $4\leftrightarrow2$，边权为 $1$；
• $4\leftrightarrow3$，边权为 $7$；
• $3\leftrightarrow5$，边权为 $3$。

若 $Q=500000$，评测程序会调用：

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

一次可能的询问过程是：

get_distance(5, 4) = 10
get_distance(2, 4) = 1
get_distance(1, 3) = 15
get_distance(1, 2) = 9

随后可以返回：

A = [3, 4, 4, 5]
B = [4, 1, 2, 3]
W = [7, 8, 1, 3]

这与真实道路集合完全相同，因此是合法答案。

数据范围

对于所有测试数据：

• $2\le N\le1000$；
• $1\le A_i,B_i\le N$；
• $1\le W_i\le10^9$；
• 道路构成一棵树；
• 每个交叉口的度数不超过 $3$。

子任务

子任务	分值	$Q$	附加限制
1	9	$500000$	所有 $W_i=1$
2	16		无附加限制
3	13	$12000$	每个点的度数不超过 $2$，且所有 $W_i=1$
4	19		每个点的度数不超过 $2$
5	43	$25000$	无附加限制，采用特殊计分

子任务 5 的计分方式

设你在子任务 5 的所有测试点中，使用询问次数最多的一次为 $q$。

• 若 $q>25000$，子任务 5 得 $0$ 分；
• 若 $12000<q\le25000$，得分为

$$10-10\cdot\frac{q-12000}{13000};$$

• 若 $6500<q\le12000$，得分为

$$40-30\cdot\frac{q-6500}{5500};$$

• 若 $q\le6500$，得到完整的 $43$ 分。

本地测试

附件中提供：

• citymapping.h：函数声明；
• citymapping.cpp：提交模板；
• grader.cpp：本地评测程序；
• compile_local.sh：Linux 编译脚本；
• samples/：每个子任务的小样例和大样例。

将这些文件放在同一目录下，只修改 citymapping.cpp，然后执行：

bash compile_local.sh
./citymapping < samples/st5_small.in

若恢复出的地图正确，本地评测程序输出：

OK 使用的询问次数

例如：

OK 12

表示地图恢复正确，共调用了 $12$ 次 get_distance。

本地 Grader 的输入格式

该格式仅供本地测试程序使用，选手提交的 find_roads 不应自行读取这些数据。

第一行包含三个整数：

N Q S

其中 $S$ 为子任务编号。

接下来 $N-1$ 行，每行三个整数：

A_i B_i W_i

表示一条真实道路。

@下发文件