P16708 [SEATST 2026] 麻烦的旅程 / Troublesome Trip

一个被称为 Nuko 的独特而神秘的物种栖息在世界偏远角落的一个群岛上。该群岛可以建模为 $N$ 个岛屿，编号从 $0$ 到 $N - 1$ ，由 $M$ 座桥梁连接。对于所有 $0 \le i \le M - 1$ ，每座桥 $i$ 双向连接两个岛屿 $U[i]$ 和 $V[i]$ 。保证可以从任意一个岛屿到达其他任意岛屿。每座桥连接两个不同的岛屿，并且没有两座桥连接相同的一对岛屿。 在远古时代，Nukos 仅居住在 $0$ 号岛屿上。然而，随着时间的推移，Nukos 已经扩散到了所有岛屿。每当一群 Nukos 穿过桥梁到达一个新岛屿时，它们就会经历进化，从而形成与前一个岛屿上不同的亚种。具体来说，对于所有 $0 \le j \le N - 1$ ，$j$ 号岛屿上的 Nukos 属于亚种 $s_j$ ，其中 $s_j$ 是从 $0$ 号岛屿到达 $j$ 号岛屿必须经过的最少桥梁数。比如， $0$ 号岛屿上的 Nukos 属于亚种 $0$ 。 你是一名旅行者，打算使用这些桥梁从 $A$ 号岛屿旅行到 $B$ 号岛屿。保证 $A \ne B$ 。当你在某个岛屿上时，你不可避免地会遇到居住在那里的 Nukos 亚种。由于每个亚种都有自己的习俗你需要适应，而适应不同的习俗可能会很麻烦，因此你的目标是选择一条路径，使得你遇到的不同 Nuko 亚种的数量最小化。 你能计算出在从 $A$ 号岛屿旅行到 $B$ 号岛屿时，你必须遇到的最少的不同 Nuko 亚种数量吗？ ### 实现详情 你需要实现以下函数。 ```cpp int min_distinct(int N, int M, int A, int B, std::vector U, std::vector V) ``` - $N$ ：岛屿的数量。 - $M$ ：桥梁的数量。 - $A$ ：你旅行的起点。 - $B$ ：你旅行的终点。 - $U$ 、 $V$ ：长度为 $M$ 的数组，描述这些桥梁。 - 此函数应返回你必须遇到的不同 Nuko 亚种的最小数量。

``` N M A B U[0] V[0] U[1] V[1] ... U[M - 1] V[M - 1] ```

一个整数，表示 `min_distinct` 函数的返回值。

### 样例 考虑以下函数调用。 ```cpp min_distinct(5, 5, 2, 4, [0, 1, 2, 3, 4], [1, 2, 3, 4, 0]) ``` 岛屿的示意图如下所示，不同的阴影代表不同的 Nuko 亚种。 :::align{center}  ::: 对于样例 $1$ ，最优路径是 $2 - 3 - 4$ 。遇到的 Nuko 亚种有 $1$ 和 $2$ 。因此，该调用应返回 $2$ 。 ```cpp min_distinct(8, 9, 4, 7, [0, 0, 0, 1, 1, 2, 2, 6, 7], [1, 2, 3, 4, 5, 5, 6, 3, 3]) ``` 岛屿的示意图如下所示，不同的阴影代表不同的 Nuko 亚种。 :::align{center}  ::: 对于样例 $2$ ，最优路径是 $4 - 1 - 5 - 2 - 6 - 3 - 7$ 。遇到的 Nuko 亚种有 $1$ 和 $2$ 。因此，该调用应返回 $2$ 。 ```cpp min_distinct(15, 17, 3, 7, [0, 1, 2, 3, 4, 13, 12, 12, 11, 10, 10, 9, 8, 7, 6, 8, 0], [1, 2, 3, 4, 13, 12, 1, 11, 10, 9, 5, 8, 7, 6, 5, 14, 14]) ``` 对于样例 $3$ ，从 $3$ 号岛屿旅行到 $7$ 号岛屿时，你必须遇到的不同 Nuko 亚种的最少数量为 $3$ 。因此，该调用应返回 $3$ 。 ### 约束 - $2 \le N \le 5\ 000\ 000$ 。 - $1 \le M \le 5\ 000\ 000$ 。 - $0 \le A, B \le N - 1$ 。 - $A \ne B$ - 对于所有 $0 \le i \le M - 1$ ， $0 \le U[i], V[i] \le N - 1$ 。 - 对于所有 $0 \le i \le M - 1$ ， $U[i] \ne V[i]$ 。 - 对于所有 $0 \le i, j \le M - 1$ 和 $i \ne j$ ， $(U[i], V[i]) \ne (U[j], V[j])$ 且 $(U[i], V[i]) \ne (V[j], U[j])$ 。 - 保证可以从任意一个岛屿到达其他任意岛屿。 ### 子任务 1. ($4$ 分) $A = 0, N \le 100\ 000, M \le 100\ 000$ 。 2. ($4$ 分) $M = N - 1, N \le 100\ 000, M \le 100\ 000$ 。 3. ($6$ 分) $N \le 300, M \le 300$ 。 4. ($8$ 分) $N \le 4\ 000, M \le 4\ 000$ 。 5. ($22$ 分) $N \le 4\ 000, M \le 1\ 000\ 000$ 。 6. ($14$ 分) $N \le 100\ 000, M \le 100\ 000$ 。 7. ($5$ 分) $N \le 300\ 000, M \le 300\ 000$ 。 8. ($5$ 分) $N \le 500\ 000, M \le 500\ 000$ 。 9. ($32$ 分) 没有额外的约束。 **注意：** 对于子任务 $9$ ，评测程序会占用 $4500$ 毫秒时间限制中的 $1500$ 毫秒。