P15824 [JOI Open 2014] 工厂 / Factories

在 IOI 王国中，有 $N$ 座城市，编号从 0 到 $N-1$。这些城市由 $N-1$ 条双向通行的道路连接。你可以通过若干条道路从任意一座城市旅行到任意另一座城市。 IOI 王国中有许多生产特殊部件的公司。每家公司只生产一种部件。没有两家公司生产同一种部件。每家公司至少有一家工厂。每座工厂都建在某座城市中。可能有不止一家公司在同一座城市设有工厂。 有时，公司 $C_A$ 需要另一家公司 $C_B$（$C_A \ne C_B$）的部件。在这种情况下，他们需要将部件从 $C_B$ 运输到 $C_A$。他们可以从公司 $C_B$ 的任意一家工厂运输到公司 $C_A$ 的任意一家工厂。他们需要适当地选择工厂，以最小化工厂之间的距离。 ### 任务 首先，给出 IOI 王国的城市数量和道路信息。然后，给出 $Q$ 个询问。每个询问的格式如下：在 $X_{j,0}, \dots, X_{j,S_j-1}$ 城市设有工厂的公司 $U_j$ 需要公司 $V_j$ 的部件，后者在 $Y_{j,0}, \dots, Y_{j,T_j-1}$ 城市设有工厂。请编写一个程序，对于每个询问，返回运输部件所需的最短距离。 ### 实现细节 你需要编写一个程序，实现处理询问的各个过程。你的程序必须通过 `#include "factories.h"` 包含头文件 `factories.h`。 你的程序需要实现以下过程。 - `void Init(int N, int A[], int B[], int D[])` 该过程在程序开始时仅被调用一次。参数 $N$ 是 IOI 王国的城市数量。参数 $A$、$B$ 和 $D$ 是长度为 $N-1$ 的数组。元素 $A[i]$、$B[i]$ 和 $D[i]$ 分别是三个整数 $A_i$、$B_i$ 和 $D_i$（$0 \le i \le N-2$）。这意味着，对于每个 $i$（$0 \le i \le N-2$），存在一条长度为 $D_i$ 的道路连接城市 $A_i$ 和城市 $B_i$。 - `long long Query(int S, int X[], int T, int Y[])` 该过程为每个询问（共 $Q$ 个）调用一次。在第 $j$ 个询问中，参数 $S$ 和 $T$ 分别是两个整数 $S_j$ 和 $T_j$，代表公司 $U_j$ 和 $V_j$ 各自拥有工厂的城市数量。参数 $X$ 是一个长度为 $S_j$ 的数组，公司 $U_j$ 在城市 $X[0], X[1], \dots, X[S-1]$ 设有工厂。参数 $Y$ 是一个长度为 $T_j$ 的数组，公司 $V_j$ 在城市 $Y[0], Y[1], \dots, Y[T-1]$ 设有工厂。该过程应返回将部件从公司 $V_j$ 运输到公司 $U_j$ 所需的最短距离。 ### 编译与测试运行 你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的样例评分器。该归档文件还包含一个你的程序的样例源文件。 样例评分器由一个源文件组成，文件名为 `grader.c` 或 `grader.cpp`。例如，如果你的程序是 `factories.c` 或 `factories.cpp`，你可以运行以下命令来编译你的程序。 - **C** ``` gcc -O2 -std=c11 -o grader grader.c factories.c -lm ``` - **C++** ``` g++ -O2 -std=c++11 -o grader grader.cpp factories.cpp ``` 编译成功后，会生成可执行文件 `grader`。 请注意，实际评测使用的评分器与样例评分器不同。样例评分器将作为单个进程运行，它会从标准输入读取输入数据，并将结果写入标准输出。

样例评分器从标准输入读取以下数据。 - 第一行包含两个以空格分隔的整数 $N$、$Q$，表示 IOI 王国有 $N$ 座城市，并且你的程序将处理 $Q$ 个询问。 - 接下来的 $(N-1)$ 行中，第 $(i+1)$ 行（$0 \le i \le N-2$）包含三个以空格分隔的整数 $A_i$、$B_i$、$D_i$，表示存在一条长度为 $D_i$ 的道路连接城市 $A_i$ 和城市 $B_i$。 - 接下来的 $3Q$ 行中，第 $j$ 个询问的信息写在从第 $(3j+1)$ 行到第 $(3j+3)$ 行（$0 \le j \le Q-1$）。 - 第 $(3j+1)$ 行（$0 \le j \le Q-1$）包含两个以空格分隔的整数 $S_j$ 和 $T_j$（$1 \le S_j \le N-1$，$1 \le T_j \le N-1$），表示公司 $U_j$ 和 $V_j$ 分别拥有 $S_j$ 和 $T_j$ 家工厂所在的城市。 - 第 $(3j+2)$ 行（$0 \le j \le Q-1$）包含 $S_j$ 个以空格分隔的整数 $X_{j,0}, \dots, X_{j,S_j-1}$，表示公司 $U_j$ 在城市 $X_{j,0}, \dots, X_{j,S_j-1}$ 设有工厂。 - 第 $(3j+3)$ 行（$0 \le j \le Q-1$）包含 $T_j$ 个以空格分隔的整数 $Y_{j,0}, \dots, Y_{j,T_j-1}$，表示公司 $V_j$ 在城市 $Y_{j,0}, \dots, Y_{j,T_j-1}$ 设有工厂。

程序成功终止后，样例评分器会将每次 `Query` 调用返回的值按行写入**标准输出**，每行一个。

### 样例 1 解释 以上是样例评分器的输入输出样例。 - 在询问 0 中，公司 $U_0$ 在城市 0、6 设有工厂，公司 $V_0$ 在城市 3、4 设有工厂。从公司 $V_0$ 位于城市 3 的工厂到公司 $U_0$ 位于城市 6 的工厂距离最短。最短距离为 12。 - 在询问 1 中，公司 $U_1$ 在城市 0、1、3 设有工厂，公司 $V_1$ 在城市 4、6 设有工厂。从公司 $V_1$ 位于城市 6 的工厂到公司 $U_1$ 位于城市 1 的工厂距离最短。最短距离为 3。 - 在询问 2 中，公司 $U_2$ 在城市 2 设有工厂，公司 $V_2$ 在城市 5 设有工厂。从公司 $V_2$ 位于城市 5 的工厂到公司 $U_2$ 位于城市 2 的工厂距离最短。最短距离为 11。 ### 约束条件 所有输入数据满足以下条件。 - $2 \le N \le 500000$。 - $1 \le Q \le 100000$。 - $0 \le A_i \le N-1$（$0 \le i \le N-2$）。 - $0 \le B_i \le N-1$（$0 \le i \le N-2$）。 - $1 \le D_i \le 100000000$（$0 \le i \le N-2$）。 - $A_i \ne B_i$（$1 \le i \le N-2$）。 - 你可以通过若干条道路从任意一座城市旅行到任意另一座城市。 - $1 \le S_j \le N-1$（$0 \le j \le Q-1$）。 - $0 \le X_{j,k} \le N-1$（$0 \le j \le Q-1$，$0 \le k \le S_j-1$）。 - $1 \le T_j \le N-1$（$0 \le j \le Q-1$）。 - $0 \le Y_{j,k} \le N-1$（$0 \le j \le Q-1$，$0 \le k \le T_j-1$）。 - $X_{j,0}, X_{j,1}, \dots, X_{j,S_j-1}, Y_{j,0}, Y_{j,1}, \dots, Y_{j,T_j-1}$ 互不相同（$0 \le j \le Q-1$）。 - $S_0 + S_1 + \cdots + S_{Q-1} \le 1000000$。 - $T_0 + T_1 + \cdots + T_{Q-1} \le 1000000$。 ### 子任务 #### 子任务 1 [15 分] 满足以下条件： - $N \le 5000$。 - $Q \le 5000$。 #### 子任务 2 [18 分] 满足以下条件： - $S_i \le 10$（$0 \le i \le Q-1$）。 - $T_i \le 10$（$0 \le i \le Q-1$）。 #### 子任务 3 [67 分] - 无额外约束。 翻译由 DeepSeek V3.2 完成