背景

在洛谷评测本题，无需使用头文件 navigation.h。

题目描述

台湾省高山密度很高，拥有超过 250 座 3000 米以上的高峰。阿明计划在台湾省的中央山脉建造机器人滑索运送网络，用以在偏远村落之间运输包裹。

在阿明的计划中，每个网络由 $N$ 个节点组成，编号从 $0$ 到 $N - 1$。这些节点中，恰好 $K = 6$ 个是发电站，其余 $N - K$ 个节点全是村庄节点。节点之间由 $N - 1$ 条双向电缆连接，电缆编号从 $0$ 到 $N - 2$。对于每个 $i$（$0 \le i \le N - 2$），电缆 $i$ 连接节点 $U[i]$ 和 $V[i]$。每条电缆连接两个不同的节点，且每对节点之间最多由一条电缆连接。保证可以借助电缆在任意两个节点之间移动。

节点 $a$ 与 $b$ 的距离记为 $d(a,b)$，其定义如下。

• 若 $a = b$，则 $d(a, b) = 0$。
• 否则，$d(a, b)$ 是从 $a$ 移动到 $b$ 所需经过的最少电缆数。

如果网络中的每个节点要么恰好连接 $1$ 条电缆，要么连接至少 $\delta$ 条电缆，我们就称该网络的分支因子至少为 $\delta$。阿明已知一个正整数 $B$，满足该网络的分支因子至少为 $B$。

阿明准备了 $100$ 种不同类型的电缆，编号为 $0, 1, \ldots, 99$。网络中的每条电缆都将采用其中一种类型进行建造。

机器人将沿着滑索电缆行驶以执行运送任务。阿明希望安装一套导航程序，帮助机器人返回发电站并给自己充电。然而，机器人的内存极低。因此，在设计导航程序时，机器人仅根据发电站数量 $K = 6$、保证的最低分支因子 $B$ 以及连接到机器人当前位置的电缆类型来进行导航。

当机器人需要在一个连接了两条或更多电缆的村庄节点 $u$ 处导航时，机器人首先以任意顺序扫描连接到 $u$ 的电缆。随后，程序会收到一个列表，按该顺序包含这些电缆的类型。对于每条电缆，程序需要统计满足“沿着该电缆能缩短机器人与发电站之间距离”这一条件的发电站数量。

具体来说，设 $v_1, \ldots, v_k$（$k \ge 2$）是通过电缆直接连接到 $u$ 的节点，$c_i$（$1 \le i \le k$）是连接节点 $u$ 与 $v_i$ 的电缆的类型。程序随后被提供 $K$、$B$ 和列表 $c_1, c_2, \ldots, c_k$。对于每个 $i$（$1 \le i \le k$），程序必须确定满足 $d(v_i, p) < d(u, p)$ 的发电站 $p$ 的数量。

你的任务是设计一套策略来分配电缆类型并编写导航程序。你的解决方案的得分取决于所用不同类型电缆的数量（详见子任务与计分部分）。

实现细节

你需要实现两个过程，一个用于分配电缆类型，另一个用于机器人的程序。

你需要实现的分配电缆类型的过程如下：

std::vector<int> construct_network(int N, int K, int B,
                                   std::vector<int> U, std::vector<int> V,
                                   std::vector<int> P)

• $N$：节点的数量。
• $K$：发电站的数量。
• $B$：网络保证的最低分支因子。
• $U, V$：长度为 $N - 1$ 的数组，描述电缆连接情况。
• $P$：长度为 $K = 6$ 的数组，描述发电站所在的节点。
• 对于每个测试用例，该过程最多会被调用 $10\,000$ 次。

该过程应返回一个长度为 $N - 1$ 的数组 $T$：

• 类型为 $T[i]$ 的电缆用于连接节点 $U[i]$ 和 $V[i]$。
• 每个元素 $T[i]$ 必须满足 $0 \le T[i] < 100$。

你需要实现的机器人程序的过程如下：

std::vector<int> navigate(int K, int B, std::vector<int> C)

• $K$：发电站的数量。
• $B$：网络保证的最低分支因子。
• $C$：连接到某个连接了至少 2 条电缆的村庄节点的所有电缆的类型列表，以任意顺序给出。
• 保证 $C$ 的长度至少为 $B$。
• 对于每个测试用例，该过程最多会被调用 $100\,000$ 次。
• 过程 navigate 不得依赖于原始网络结构；特别地，评测系统可能会在同一个测试用例的不同构建网络之间，对所有 navigate 调用进行重排。

该过程应返回一个数组 $D$：

• 数组 $D$ 的长度必须与数组 $C$ 相同。
• $D[i]$ 必须是沿着 $C[i]$ 所对应的电缆移动后，能缩短机器人与发电站之间距离的发电站数量。

请注意，在评测系统中，construct_network 和 navigate 过程是在两个独立的进程中被调用的。

输入格式

样例评测器在同一个进程中调用 construct_network 和 navigate。此外，当样例评测器调用 navigate 时，电缆类型按照其在输入中出现的顺序列出。这两种行为均与实际评测器不同。

输入格式：

T
(场景 0)
(场景 1) 
...
(场景 T-1) 

每个场景的格式如下：

N
B
U[0] V[0]
U[1] V[1]
...
U[N-2] V[N-2]
K
P[0] P[1] ... P[K-1]
Q
X[0] X[1] ... X[Q-1]

在每个场景中，样例评测器会调用 navigate 共 $Q$ 次，第 $i$ 次调用携带节点 $X[i - 1]$ 的信息。请注意，样例评测器支持将 $K$ 设为 $6$ 以外的其他整数。

输出格式

如果 construct_network 或 navigate 返回的任一数组不合法，样例评测器将中止并打印原因。否则，样例评测器将每次 navigate 调用返回的数组 $D$ 输出为一行。

当所有场景处理完毕后，样例评测器向标准错误输出一行：

S = S'

其中 $S'$ 是大于该测试用例中每次 construct_network 调用返回的数组 $T$ 中所有数字的最小整数。

提示

样例

考虑这样一个场景：$N = 9$，$K = 6$，$B = 2$。

网络方案由 $U = [0,0,0,2,2,2,2,7]$、$V = [1,2,3,4,5,6,7,8]$ 指定。发电站为 $P = [1,3,4,5,6,7]$。考虑对第一个进程的如下调用：

construct_network(9, 6, 2, [0, 0, 0, 2, 2, 2, 2, 7],
                  [1, 2, 3, 4, 5, 6, 7, 8],
                  [1, 3, 4, 5, 6, 7])

假设阿明通过返回以下数组来构建网络：

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

构建的网络如下图所示。

:::align{center} :::

随后，在第二个进程中，假设机器人需要在节点 $0$ 处导航。节点 $0$ 连接到节点 $1$、$2$ 和 $3$。如果机器人按此顺序读取电缆类型，将会进行以下调用：

navigate(6, 2, [0, 10, 1])

根据网络结构：

• 第一个发电站，节点 $1$，到其自身距离最短。具体来说，$0 = d(1,1) < 1 = d(0,1) < 2 = d(2,1) = d(3,1)$。
• 第二个发电站，节点 $3$，到其自身距离最短。具体来说，$0 = d(3,3) < 1 = d(0,3) < 2 = d(1,3) = d(2,3)$。
• 其他发电站，节点 $4$、$5$、$6$ 和 $7$，到节点 $2$ 的距离更短。具体来说，当 $u = 4,5,6$ 或 $7$ 时，$1 = d(2,u) < 2 = d(0,u) < 3 = d(1,u) = d(3,u)$。

沿着电缆 $(0,1)$、$(0,2)$ 和 $(0,3)$ 移动后，距离缩短的发电站数量分别为 $1$、$4$ 和 $1$。因此，该过程应返回：

[1, 4, 1]

请注意，navigate 也可能以 $C$ 的不同排列被调用。例如，对于节点 $0$，navigate(6, 2, [1, 0, 10]) 也是一种可能的调用。此时，过程应返回 [1, 1, 4]。

假设机器人需要在节点 $2$ 处导航。将进行以下调用：

navigate(6, 2, [10, 2, 3, 4, 5])

过程应返回：

[2, 1, 1, 1, 1]

在此网络中，对于其他节点，navigate 过程将永不被调用，这是因为：

• 节点 $1$、$3$、$4$、$5$、$6$ 和 $7$ 都是发电站，且
• 节点 $8$ 只连接了一条电缆。

在此测试用例中，所用到的电缆类型为 $0$、$1$、$2$、$3$、$4$、$5$ 和 $10$。因此，$S = 11$ 将用于确定得分。

除本例外，本题的附件包还包含另外两个供样例评测器使用的样例输入和输出。

数据范围

• $K = 6$。
• $K < N \le 100\,000$。
• 在每个测试用例中，所有 construct_network 调用的 $N$ 之和不超过 $100\,000$。
• 对于每个 $0 \le i \le N - 2$，有 $0 \le U[i] < V[i] < N$。
• 可以借助电缆从任意节点移动到任意其他节点。
• $0 \le P[0] < P[1] < \cdots < P[K-1] < N$。
• 每个数组 $C$ 是连接到某个连接了至少 $2$ 条电缆的村庄节点的所有电缆的类型列表的一个排列。
• 在每个测试用例中，所有 navigate 调用的数组 $C$ 的长度之和不超过 $200\,000$。

子任务与计分

子任务	分值	附加约束
$1$	$6$	$B = 2, N = 7$。
$2$	$14$	$B = 2$，对每个满足 $0 \le i < N - 1$ 的 $i$，有 $U[i] = i, V[i] = i + 1$。
$3$	$20$	$B = 5$。
$4$		$B = 4$。
$5$	$40$	$B = 2$。

在任何测试用例中，如果至少满足下列条件之一，则你对于该测试用例的解答得分为 $0$（在 CMS 中报告为“输出不正确”）：

• 任意一次 construct_network 调用的返回值不合法。
• 任意一次 navigate 调用的返回值不正确。

否则，令 $S$ 为大于每次 construct_network 调用返回的数组 $T$ 中所有数字的最小整数。换言之，$S$ 是使得所有构建的网络仅使用类型为 $0, 1, \ldots, S - 1$ 的电缆的最小整数。

你在每个子任务上的得分取决于 $S$，具体如下表：

条件	子任务 1	子任务 2	子任务 3 和 4	子任务 5
$100 < S$	$0$
$16 \le S \le 100$	$2$	$2$	$12 - \log_2 S$	$24 - 2\log_2 S$
$10 \le S \le 15$		$4$	$16 - 0.5S$	$32 - S$
$7 \le S \le 9$		$6$	$21 - S$	$42 - 2S$
$S = 6$		$10$	$15$	$30$
$S = 5$	$\bm6$	$\bm{14}$	$17.5$	$\bm{40}$
$S \le 4$			$\bm{20}$

特别地，在子任务 $1$、$2$ 和 $5$ 中，如果你能做到 $S \le 5$，即可获得满分；在子任务 $3$ 和 $4$ 中，如果你能做到 $S \le 4$，即可获得满分。

翻译由 DeepSeek V4 Pro 完成