시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

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 C_{A} requires the components of the company C_{B} (C_{A}, C_{B}). In this case, they need to transport components from C_{B} to C_{A}. They may transport components from any of the factories of the company C_{B} to any of the factories of the company C_{A}. 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 U_{j} having factories in cities X_{j,0}, . . . , X_{j,Sj−1} requires components of the company V_{j} having factories in cities Y_{j,0}, . . . , Y_{j,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 A_{i}, B_{i} and D_{i} (0 ≤ i ≤ N − 2) respectively. This means, for each i (0 ≤ i ≤ N − 2), there is a road of length D_{i} connecting the city A_{i} and the city B_{i}.

`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 S_{j} and T_{j} respectively. These are the numbers of cities where the companies U_{j}, V_{j} have factories respectively.

The parameter X is an array of length S_{j}. The company U_{j} has factories in cities X[0], X[1], . . . , X[S-1].

The parameter Y is an array of length T_{j}. The company V_{j} has factories in cities Y[0], Y[1], . . . , Y[T-1].

This procedure should return the minimum distance to transport components from the company V_{j} to the company U_{j}.

- The first line contains two space separated integers N, Q, which means there are N cities in IOI Kingdom, and Q queries are given to your program.
- The (i + 1)-st line (0 ≤ i ≤ N − 2) of the following (N − 1) lines contains three space separated integers Ai,Bi, Di, which means there is a road of length Di connecting the city Ai and the city Bi.
- The information of the j-th query is written from the (3j + 1)-st line to the (3j + 3)-rd line (0 ≤ j ≤ Q − 1) of the following 3Q lines.
- The (3j + 1)-st line (0 ≤ j ≤ Q − 1) contains two space separated integers S
_{j}and T_{j}(1 ≤ S_{j}≤ N − 1, 1 ≤ T_{j}≤ N − 1), which means the companies U_{j}and V_{j}have factories in S_{j}and T_{j}cities respectively. - The (3j + 2)-nd line (0 ≤ j ≤ Q − 1) contains S
_{j}space separated integers X_{j,0}, . . . , X_{j,Sj−1}, which means the company U_{j}has factories in the cities X_{j,0}, . . . , X_{j,Sj−1}. - The (3j + 3)-rd line (0 ≤ j ≤ Q − 1) contains T
_{j}space separated integers Y_{j,0}, . . . , Y_{j,Tj−1}, which means the company Vj has factories in the cities Y_{j,0}, . . . , Y_{j,Tj−1}.

All input data satisfy the following conditions.

- 2 ≤ N ≤ 500 000.
- 1 ≤ Q ≤ 100 000.
- 0 ≤ A
_{i}≤ N − 1 (0 ≤ i ≤ N − 2). - 0 ≤ B
_{i}≤ N − 1 (0 ≤ i ≤ N − 2). - 1 ≤ D
_{i}≤ 100 000 000 (0 ≤ i ≤ N − 2). - A
_{i}, B_{i}(1 ≤ i ≤ N − 2). - You can travel from any city to any other city through some of these roads.
- 1 ≤ S
_{j}≤ N − 1 (0 ≤ j ≤ Q − 1). - 0 ≤ X
_{j,k}≤ N − 1 (0 ≤ j ≤ Q − 1, 0 ≤ k ≤ S_{j}− 1). - 1 ≤ T
_{j}≤ N − 1 (0 ≤ j ≤ Q − 1). - 0 ≤ Y
_{j,k}≤ N − 1 (0 ≤ j ≤ Q − 1, 0 ≤ k ≤ T_{j}− 1). - X
_{j,0}, X_{j,1}, . . . , X_{j,Sj−1}, Y_{j,0}, Y_{j,1}, . . . , Y_{j,Tj−1}are different from each other (0 ≤ j ≤ Q − 1) ． - S
_{0}+ S_{1}+ · · · + S_{Q−1}≤ 1 000 000. - T
_{0}+ T_{1}+ · · · + T_{Q−1}≤ 1 000 000.

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.

- In the query 0, the company U
_{0}has factories in the cities 0, 6, and the company V_{0}has factories in the cites 3, 4. The distance from the factory of the company V_{0}in the city 3 to the factory of the company U_{0}in the city 6 is minimum. The minimum distance is 12. - In the query 1, the company U
_{1}has factories in the cities 0, 1, 3, and the company V_{1}has factories in the cites 4, 6. The distance from the factory of the company V_{1}in the city 6 to the factory of the company U_{1}in the city 1 is minimum. The minimum distance is 3. - In the query 2, the company U
_{2}has factories in the city 2, and the company V_{2}has factories in the city 5. The distance from the factory of the company V_{2}in the city 5 to the factory of the company U_{2}in the city 2 is minimum. The minimum distance is 11.