注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

题目描述

译自 JOI Open 2014 Day1 T1「工場 / Factories」

在 IOI 王国，有 $N$ 个城市，编号从 $0$ 到 $N-1$。这些城市由 $N-1$ 条双向道路相连。你可以通过这些道路从任何一个城市到达另一个城市。

在 IOI 王国，有许多公司生产特殊的零件。每个公司只生产一种零件。没有两个公司生产相同的零件。每个公司至少有一个工厂。每个工厂建在一个城市里。同一个城市里可能有多个公司的工厂。

在某些情况下，一个公司需要另一个公司的零件。假设公司 $C_{A}$ 需要公司 $C_{B}\ (C_{A} \neq C_{B})$ 的零件，他们需要将零件从 $C_{B}$ 运输到 $C_{A}$。他们可以从公司 $C_{B}$ 的任何一个工厂运输零件到公司 $C_{A}$ 的任何一个工厂。他们需要合理地选择工厂，以使工厂之间的距离最小。

给出 IOI 王国的城市数和道路的信息。有 $Q$ 个询问。每个询问的形式如下：公司 $U_{j}$ 在城市 $X_{j, 0}, \ldots, X_{j, S_{j}-1}$ 有工厂，公司 $V_{j}$ 在城市 $Y_{j, 0}, \ldots, Y_{j, T_{j}-1}$ 有工厂。公司 $U_{j}$ 需要公司 $V_{j}$ 的零件。编写一个程序，对于每个询问，返回运输零件的最小距离。

实现细节

你需要编写一个程序，实现回答询问的函数。你的程序应该包含头文件 factories.h，你的程序应该实现以下函数。

• $\texttt{void Init(int N, int A[], int B[], int D[])}$

  这个函数只在开始时调用一次。

  • 参数 $\texttt{N}$ 表示 IOI 王国的城市数。
  • 参数 $\texttt{A,B,D}$ 是长度为 $N-1$ 的数组。元素 $\texttt{A[i],B[i],D[i]}$ 分别代表 $A_{i},B_{i},D_{i}\ (0 \leq i \leq N-2)$。表示对于每个 $i\ (0 \leq i \leq N-2)$，有一条长度为 $D_{i}$ 的道路连接城市 $A_{i}$ 和城市 $B_{i}$。

• $\texttt{long long Query(int S, int X[], int T, int Y[])}$

  这个函数对于每个 $Q$ 个询问都会被调用。在询问 $j$ 中：

  • 参数 $\texttt{S}$ 和 $\texttt{T}$ 是两个整数 $S_{j}$ 和 $T_{j}$，分别表示公司 $U_{j}, V_{j}$ 的工厂所在城市的数量。
  • 参数 $\texttt{X}$ 是一个长度为 $S_{j}$ 的数组，表示公司 $U_{j}$ 在城市 $\texttt{X}[0], \texttt{X}[1], \ldots, \texttt{X}[\texttt{S}-1]$ 有工厂。
  • 参数 $\texttt{Y}$ 是一个长度为 $T_{j}$ 的数组，表示公司 $V_{j}$ 在城市 $\texttt{Y}[0], \texttt{Y}[1], \ldots, \texttt{Y}[\texttt{T}-1]$ 有工厂。
  • 这个函数应该返回从公司 $V_{j}$ 到公司 $U_{j}$ 运输零件的最小距离。

编译和测试运行

你可以从「文件」页面下载样例交互器并测试你的程序。「文件」页面也包含一个样例源文件。

样例交互器是文件 grader.cpp。为了测试你的程序，你需要将 grader.cpp，factories.cpp 和 factories.h 三个文件放在同一文件夹下，并运行如下命令编译你的程序。

g++ -02 -std=c++11 -o grader grader.cpp factories.cpp

当编译成功后，会产生一个可执行文件 grader。

请注意实际的交互器和样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入，并输出结果到标准输出。

样例交互器输入

第一行包含两个用空格分隔的整数 $N, Q$，表示IOI王国有 $N$ 个城市，给你的程序有 $Q$ 个询问。

接下来的 $N-1$ 行中的第 $i+1\ (0 \leq i \leq N-2)$ 行包含三个用空格分隔的整数 $A_{i}, B_{i}, D_{i}$，表示有一条长度为 $D_{i}$ 的道路连接城市 $A_{i}$ 和城市 $B_{i}$。

接下来的 $3Q$ 行中，从第 $3j+1\ (0 \leq j \leq Q-1)$ 行到第 $3j+3$ 行包含第 $j$ 个询问的信息。

第$3j+1\ (0 \leq j \leq Q-1)$ 行包含两个用空格分隔的整数 $S_{j}\ (1 \leq S_{j} \leq N-1)$ 和 $T_{j}\ (1 \leq T_{j} \leq N-1)$，表示公司 $U_{j}$ 和 $V_{j}$ 分别在 $S_{j}$ 和 $T_{j}$ 个城市有工厂。

第 $3j+2\ (0 \leq j \leq Q-1)$ 行包含 $S_{j}$ 个用空格分隔的整数 $X_{j, 0}, \ldots, X_{j, S_{j}-1}$，表示公司 $U_{j}$ 在城市 $X_{j, 0}, \ldots, X_{j, S_{j}-1}$ 有工厂。

第 $3j+3\ (0 \leq j \leq Q-1)$ 行包含$T_{j}$ 个用空格分隔的整数 $Y_{j, 0}, \ldots, Y_{j, T_{j}-1}$，表示公司 $V_{j}$ 在城市 $Y_{j, 0}, \ldots, 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

这些是样例评测器的样例输入和样例输出。

• 在查询 $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 \leq N \leq 5\times 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq A_{i} \leq N-1\ (0 \leq i \leq N-2)$
• $0 \leq B_{i} \leq N-1\ (0 \leq i \leq N-2)$
• $1 \leq D_{i} \leq 10^9\ (0 \leq i \leq N-2)$
• $A_{i} \neq B_{i}\ (1 \leq i \leq N-2)$
• 你可以通过这些道路从任何一个城市到达另一个城市
• $1 \leq S_{j} \leq N-1\ (0 \leq j \leq Q-1)$
• $0 \leq X_{j, k} \leq N-1\ (0 \leq j \leq Q-1,0 \leq k \leq S_{j}-1)$
• $1 \leq T_{j} \leq N-1\ (0 \leq j \leq Q-1)$
• $0 \leq Y_{j, k} \leq N-1\ (0 \leq j \leq Q-1,0 \leq k \leq T_{j}-1)$
• $X_{j, 0}, X_{j, 1}, \ldots, X_{j, S_{j}-1}, Y_{j, 0}, Y_{j, 1}, \ldots, Y_{j, T_{j}-1}$ 彼此不同 $(0 \leq j \leq Q-1)$
• $S_{0}+S_{1}+\cdots+S_{Q-1} \leq 10^6$
• $T_{0}+T_{1}+\cdots+T_{Q-1} \leq 10^6$

详细子任务附加限制及分值如下表所示。