공장들 Batch Compilation commands

IOI 왕국에서 $0$ 이상 $N-1$ 이하의 번호가 붙은 $N$개의 도시들이 있습니다. 이들 도시들은 양방향으로 통행이 가능한 $N-1$개의 도로로 연결되어 있습니다. 여러분은 이러한 도로들을 몇 개 통과하여 어떤 서로 다른 두 다시 사이도 이동할 수 있습니다.

IOI 왕국에는 특별한 제품들을 생산하는 많은 회사들이 있습니다. 각 회사는 단 한 종류의 제품만 생산하며, 어떤 두 회사도 같은 종류의 제품을 생산하지 않습니다. 각 도시는 한 개 이상의 공장을 가지고 있습니다. 각 공장은 도시들 중 하나에 지어져 있습니다. 같은 도시에 두 개 이상의 회사가 공장을 가지고 있을 수도 있습니다.

가끔 어떤 회사는 또다른 회사의 제품이 필요할 때가 있습니다. 회사 $C_{A}$가 회사 $C_{B}$의 제품이 필요하다고 가정해 봅시다. ($C_{A} \neq C_{B}$) 이 경우, 그들은 $C_{B}$에서 $C_{A}$로 제품을 운반해야 합니다. 이를 위해 회사 $C_{B}$의 아무 공장에서 회사 $C_{A}$의 아무 공장으로 제품을 운반하면 됩니다. 그들은 공장들 사이의 거리를 최소화하기 위하여 공장들을 적절히 선택해야 합니다.

해야 할 일

우선, 도시들의 수와 IOI 왕국의 도로의 정보가 주어집니다. 그 다음, $Q$개의 질의가 주어집니다. 각 질의는 다음과 같은 형태로 주어집니다: $X_{j,0}, \cdots, X_{j, S_{j}-1}$번 도시들에 공장을 가지고 있는 회사 $U_{j}$는 $Y_{j,0}, \cdots, Y_{j, T_{j}-1}$번 도시들에 공장을 가지고 있는 회사 $V_{j}$의 제품이 필요합니다. 각 질의마다, 제품을 운반하기 위해 필요한 최소 거리를 반환하는 프로그램을 작성하세요.

구현 세부 사항

여러분은 질의에 답하는 프로그램을 구현해야 합니다. 여러분의 프로그램은 #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$)에 대해, 도시 $A_{i}$와 도시 $B_{i}$를 연결하는 길이가 $D_{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], ..., X[S-1]번 도시에 공장을두고 있습니다. Y는 길이가 $T_{j}$인 배열입니다. $V_{j}$번 회사는 Y[0], Y[1], ..., Y[T-1]번 도시에 공장을두고 있습니다.

이 함수는 회사 $V_{j}$에서 회사 $U_{j}$로 제품을 운반하기 위한 최소 거리를 반환해야 합니다.

컴파일 및 실험

여러분은 factories.zip에서 여러분의 프로그램을 시험할 간단한 채점기를 내려받을 수 있습니다. 이 파일에는 여러분이 작성할 프로그램의 예시도 들어 있습니다.

간단한 채점기는 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}$가 공백을 사이로 두고 주어집니다. 이것은 도시 $A_{i}$와 도시 $B_{i}$를 잇는 길이가 $D_{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}$가 공백을 사이로 두고 주어집니다. 이것은 회사 $U_{j}$와 회사 $V_{j}$ 각각 $S_{j}$개와 $T_{j}$개의 도시에 공장을 두고 있다는 것을 의미합니다.

$(3j+2)$번째 줄 ($0 \le j \le Q-1$)에는 $S_{j}$개의 정수 $X_{j,0}, \cdots, X_{j,S_{j}-1}$이 공백을 사이로 두고 주어집니다. 이것은 회사 $U_{j}$가 도시 $X_{j,0}, \cdots, X_{j,S_{j}-1}$에 공장을 두고 있다는 것을 의미합니다.

$(3j+3)$번째 줄 ($0 \le j \le Q-1$)에는 $T_{j}$개의 정수 $Y_{j,0}, \cdots, X_{j,T_{j}-1}$이 공백을 사이로 두고 주어집니다. 이것은 회사 $V_{j}$가 도시 $Y_{j,0}, \cdots, X_{j,T_{j}-1}$에 공장을 두고 있다는 것을 의미합니다.

예제 채점기의 출력 형식

프로그램이 성공적으로 종료되었다면, 예제 그레이더는 표준 출력에 Query에 의해 반환된 값들을 한 줄에 하나씩 차례대로 출력합니다.

제약 조건

모든 입력 데이터는 다음 조건을 만족합니다.

• $2 \le N \le 500,000$
• $1 \le Q \le 100,000$
• $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 100,000,000$ ($0 \le i \le N-2$)
• $A_{i} \neq B_{i}$ ($1 \le i \le N-2$)
• 여러분은 도로들을 통해 한 도시에서 다른 모든 도시로 이동할 수 있습니다.
• $1 \le S_{j} \le N-1$ ($0 \le j \le Q-1$)
• $1 \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$)
• $1 \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},\cdots,X_{j,S_{j}-1},Y_{j,0},Y_{j,1},\cdots,Y_{j,T_{j}-1}$은 서로 다릅니다. ($0 \le j \le Q-1$)
• $S_{0} + S_{1} + \cdots + S_{Q-1} \le 1,000,000$
• $T_{0} + T_{1} + \cdots + T_{Q-1} \le 1,000,000$

서브태스크

서브태스크 1 [15점]

• $N \le 5,000$
• $Q \le 5,000$

서브태스크 2 [18점]

• $S_{i} \le 10$ ($0 \le i \le Q-1$)
• $T_{i} \le 10$ ($0 \le i \le Q-1$)

서브태스크 3 [67점]

추가 제약 조건이 없습니다.

예제 입력 및 출력

입력

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번 도시에 공장을 두었습니다. 3번 도시에 있는 $V_{0}$의 공장에서부터 6번 도시에 있는 $U_{0}$의 공장까지의 거리가 최소입니다. 최소 거리는 12입니다.
• 1번 질의에서, 회사 $U_{1}$는 0번, 1번, 3번 도시에 공장을 두었고, 회사 $V_{1}$는 4번, 6번 도시에 공장을 두었습니다. 6번 도시에 있는 $V_{1}$의 공장에서부터 1번 도시에 있는 $U_{1}$의 공장까지의 거리가 최소입니다. 최소 거리는 3입니다.
• 2번 질의에서, 회사 $U_{2}$는 2번 도시에 공장을 두었고, 회사 $V_{2}$는 5번 도시에 공장을 두었습니다. 5번 도시에 있는 $V_{2}$의 공장에서부터 2번 도시에 있는 $U_{2}$의 공장까지의 거리가 최소입니다. 최소 거리는 11입니다.