题目描述

在 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 调用返回的值按行写入标准输出，每行一个。

7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5

12
3
11

提示

样例 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 完成