문제
IOI 왕국에는 0부터 N-1까지 번호가 매겨진 N개의 도시가 있습니다. 이 도시들은 양방향으로 통행할 수 있는 N-1개의 도로로 연결되어 있습니다. 어떤 도시에서든 다른 도시로 이동하려면 이 도로들 중 일부를 이용하면 됩니다. 각 i (0 ≤ i ≤ N-2)에 대해, 도시 Ai와 도시 Bi를 연결하는 길이 Di의 도로가 존재합니다.
IOI 왕국에는 특수 부품을 생산하는 여러 회사가 있습니다. 각 회사는 한 종류의 부품만 생산하며, 두 회사가 동일한 종류의 부품을 생산하는 경우는 없습니다. 각 회사는 최소 하나 이상의 공장을 보유하고 있으며, 각 공장은 여러 도시에 건설됩니다. 한 도시에 여러 회사가 공장을 보유할 수도 있습니다.
때때로 한 회사가 다른 회사의 부품을 필요로 하는 경우가 있습니다. 예를 들어, 회사 U가 회사 V의 부품이 필요하다고 가정해 보겠습니다(U, V). 이 경우, U는 V에서 U로 부품을 운송해야 합니다. 이때 운송을 시작하는 공장과 운송 목적지는 U와 V의 공장들 중에서 적절하게 하나를 선택할 수 있습니다. 따라서 공장 간 거리를 최소화하기 위해 적절한 공장을 선택해야 합니다.
IOI 왕국의 도시 개수와 도로 정보가 주어집니다. 그 다음, Q개의 질의가 주어집니다. 각 질의는 다음과 같은 형식으로 작성됩니다. S개의 공장을 도시 X[0], X[1], ..., X[S-1]에 보유한 회사 U가 T개의 공장을 도시 Y[0], Y[1], ..., Y[T-1]에 보유한 회사 V의 부품을 필요로 합니다. 각 질의에 대해 부품을 운송하는 최소 거리를 반환하는 프로그램을 작성하세요.
입력
첫 번째 줄에는 공백으로 구분된 두 개의 정수 N, Q가 주어집니다. 이는 IOI 왕국에 N개의 도시가 있고, 프로그램에 Q개의 쿼리가 제공된다는 것을 의미합니다.
다음 (N − 1)개 줄의 (i + 1)번째 줄(0 ≤ i ≤ N − 2)에는 공백으로 구분된 세 개의 정수 Ai, Bi, Di가 주어집니다. 이는 도시 Ai와 도시 Bi를 연결하는 길이 Di의 도로가 있음을 의미합니다.
다음 3Q개의 줄에는 쿼리의 정보가 주어집니다. j번째 쿼리(0 ≤ j ≤ Q − 1)의 정보는 다음 3Q개의 줄 중 (3j + 1)번째 줄부터 (3j + 3)번째 줄에 있습니다.
(3j + 1)번째 줄(0 ≤ j ≤ Q − 1)에는 공백으로 구분된 두 정수 S와 T(1 ≤ S ≤ N − 1, 1 ≤ T ≤ N − 1)가 포함되어 있으며, 이는 회사 U와 V가 S에 공장을 가지고 있음을 의미합니다. 그리고 각각 T 도시들입니다.
(3j + 2)번째 줄(0 ≤ j ≤ Q − 1)에는 S개의 공백으로 구분된 정수 X[0], ..., X[S-1]가 주어집니다. 이는 회사 U가 도시 X[0], ..., X[S-1]에 공장을 가지고 있음을 의미합니다.
(3j + 3)번째 줄(0 ≤ j ≤ Q − 1)에는 T개의 공백으로 구분된 정수 Y[0], ..., Y[T-1]가 주어집니다. 이는 회사 V가 도시 Y[0], ..., Y[T-1]에 공장을 가지고 있음을 의미합니다.
모든 입력 데이터는 다음 조건을 만족합니다.
2 ≤ N ≤ 500,000.
1 ≤ Q ≤ 100,000.
0 ≤ Ai ≤ N − 1 (0 ≤ i ≤ N − 2).
0 ≤ Bi ≤ N − 1 (0 ≤ i ≤ N − 2).
1 ≤ Di ≤ 100 000 000 (0 ≤ i ≤ N − 2).
Ai ≠ Bi (1 ≤ i ≤ N − 2).
이 도로들 중 일부를 이용하면 어느 도시에서든 다른 도시로 이동할 수 있습니다.
각 쿼리는 다음 조건을 만족합니다.
1 ≤ S ≤ N − 1.
0 ≤ X[k] ≤ N − 1 (0 ≤ k ≤ S − 1).
1 ≤ T ≤ N − 1
0 ≤ Y[k] ≤ N − 1 (0 ≤ k ≤ T − 1).
X[0], X[1], ..., X[S-1], Y[0], Y[1], ..., Y[T-1]은 서로 다릅니다.
S들의 합은 1,000,000을 초과하지 않습니다.
T들의 합은 1,000,000을 초과하지 않습니다.
출력
Q개의 줄에 걸쳐, 각 쿼리에 대한 정답을 출력합니다. 한 회사의 공장에서 다른 회사의 공장까지 부품을 운송하는 최소 거리를 출력하면 됩니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | N ≤ 5 000, Q ≤ 5 000. |
| #2 | 18점 | 모든 쿼리에서 S, T ≤ 10. |
| #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과 6에 공장을, 회사 V는 도시 3과 4에 공장을 보유하고 있습니다. 도시 3에 있는 회사 V의 공장에서 도시 6에 있는 회사 U의 공장으로 움직이는 게 이동거리 12로 최소입니다.
쿼리 1에서, 회사 U는 도시 0, 1, 3에 공장을, 회사 V는 도시 4, 6에 공장을 보유하고 있습니다. 도시 6에 있는 회사 V의 공장에서 도시 1에 있는 회사 U의 공장으로 움직이는 게 이동거리 3으로 최소입니다.
쿼리 2에서, 회사 U는 도시 2에 공장을, 회사 V는 도시 5에 공장을 가지고 있습니다. 도시 5에 있는 회사 V의 공장에서 도시 2에 있는 회사 U의 공장으로 움직이는 게 이동거리 11로 최소입니다.
로그인해야 코드를 작성할 수 있어요.