P16453 [APIO 2026] Navigation（暂无数据）
题目描述
台湾高山密度很高，拥有超过 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$ 的数量。
你的任务是设计一套策略来分配电缆类型并编写导航程序。你的解决方案的得分取决于所用不同类型电缆的数量（详见子任务与计分部分）。
### 实现细节
你需要实现两个过程，一个用于分配电缆类型，另一个用于机器人的程序。
你需要实现的**分配电缆类型**的过程如下：
```cpp
std::vector construct_network(int N, int K, int B,
std::vector U, std::vector V,
std::vector 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$。
你需要实现的**机器人程序**的过程如下：
```cpp
std::vector navigate(int K, int B, std::vector 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$ | $20$ | $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$ | $0$ | $0$ | $0$ |
| $16 \le S \le 100$ | $2$ | $2$ | $12 - \log_2 S$ | $24 - 2\log_2 S$ |
| $10 \le S \le 15$ | $2$ | $4$ | $16 - 0.5S$ | $32 - S$ |
| $7 \le S \le 9$ | $2$ | $6$ | $21 - S$ | $42 - 2S$ |
| $S = 6$ | $2$ | $10$ | $15$ | $30$ |
| $S = 5$ | $\bm6$ | $\bm{14}$ | $17.5$ | $\bm{40}$ |
| $S \le 4$ | $\bm6$ | $\bm{14}$ | $\bm{20}$ | $\bm{40}$ |
特别地，在子任务 $1$、$2$ 和 $5$ 中，如果你能做到 $S \le 5$，即可获得满分；在子任务 $3$ 和 $4$ 中，如果你能做到 $S \le 4$，即可获得满分。
翻译由 DeepSeek V4 Pro 完成