|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|6 초||512 MB||10||2||2||100.000%|
In IOI Kingdom, there are N cities numbered from 0 to N−1. These cities are connected by N−1 roads through which you can pass in both directions. You can travel from any city to any other city by passing through some of these roads.
In IOI Kingdom, there are many companies producing special components. Each company produces only one kind of components. No two companies produce the same kind of components. Each company has at least one factory. Each factory is built in one of the cities. More than one company may have factories in the same city.
Sometimes, a company requires components of another company. Assume the company CA requires the components of the company CB (CA, CB). In this case, they need to transport components from CB to CA. They may transport components from any of the factories of the company CB to any of the factories of the company CA. They need to choose factories appropriately to minimize the distance between factories.
First, the number of cities and the information of roads in IOI Kingdom are given. Then, Q queries are given. Each query is written in the following form: the company Uj having factories in cities Xj,0, . . . , Xj,Sj−1 requires components of the company Vj having factories in cities Yj,0, . . . , Yj,Tj−1. Write a program which, for each query, returns the minimum distance to transport the components.
You are to write a program which implements procedures to answer the queries.
Your program should include the header file factories.h by #include "factories.h"
Your program should implement the following procedures.
void Init(int N, int A, int B, int D)
This procedure is called only once in the beginning. The parameter N is the number of cities in IOI Kingdom. The parameters A, B and D are arrays of length N − 1. The elements A[i], B[i] and D[i] are three integers Ai, Bi and Di (0 ≤ i ≤ N − 2) respectively. This means, for each i (0 ≤ i ≤ N − 2), there is a road of length Di connecting the city Ai and the city Bi.
long long Query(int S, int X, int T, int Y)
This procedure is called for each of Q queries. In the query j, the parameters S and T are two integers Sj and Tj respectively. These are the numbers of cities where the companies Uj, Vj have factories respectively.
The parameter X is an array of length Sj. The company Uj has factories in cities X, X, . . . , X[S-1].
The parameter Y is an array of length Tj. The company Vj has factories in cities Y, Y, . . . , Y[T-1].
This procedure should return the minimum distance to transport components from the company Vj to the company Uj.
All input data satisfy the following conditions.
When the program terminates successfully, the sample grader writes to the standard output the values returned by Query one per line.
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
These are sample input and sample output of the sample grader.