시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 10 2 2 100.000%

문제

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

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

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

우선, 도시들의 수와 IOI 왕국의 도로의 정보가 주어집니다. 그 다음, Q개의 질의가 주어집니다. 각 질의는 다음과 같은 형태로 주어집니다: Xj,0,⋯,Xj,Sj−1번 도시들에 공장을 가지고 있는 회사 Uj는 Yj,0,⋯,Yj,Tj−1번 도시들에 공장을 가지고 있는 회사 Vj의 제품이 필요합니다. 각 질의마다, 제품을 운반하기 위해 필요한 최소 거리를 반환하는 프로그램을 작성하세요.

입력

첫 번째 줄에 두 개의 정수 N과 Q가 공백을 사이로 두고 주어집니다. 이는 IOI 왕국에 N개의 도시가 있고, 여러분의 프로그램에게 Q개의 질의가 주어진다는 것을 의미합니다.

다음 (N−1)개의 줄 중 (i+1)번째 줄 (0 ≤ i ≤ N−2)에는 세 개의 정수 Ai, Bi, Di가 공백을 사이로 두고 주어집니다. 이것은 도시 Ai와 도시 Bi를 잇는 길이가 Di인 도로가 있다는 것을 의미합니다.

다음 3Q개 줄 중에서 j번째 질의의 정보는 (3j+1)번째 줄부터 (3j+3)번째 줄까지 (0 ≤ j ≤ Q−1) 주어집니다.

(3j+1)번째 줄 (0 ≤ j ≤ Q−1)에는 두 개의 정수 Sj와 Tj가 공백을 사이로 두고 주어집니다. 이것은 회사 Uj와 회사 Vj 각각 Sj개와 Tj개의 도시에 공장을 두고 있다는 것을 의미합니다.

(3j+2)번째 줄 (0 ≤ j ≤ Q−1)에는 Sj개의 정수 Xj,0,⋯,Xj,Sj−1이 공백을 사이로 두고 주어집니다. 이것은 회사 Uj가 도시 Xj,0,⋯,Xj,Sj−1에 공장을 두고 있다는 것을 의미합니다.

(3j+3)번째 줄 (0 ≤ j ≤ Q−1)에는 Tj개의 정수 Yj,0,⋯,Yj,Tj−1이 공백을 사이로 두고 주어집니다. 이것은 회사 Vj가 도시 Yj,0,⋯,Yj,Tj−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 ≤ Sj ≤ N − 1 (0 ≤ j ≤ Q − 1).
  • 0 ≤ Xj,k ≤ N − 1 (0 ≤ j ≤ Q − 1, 0 ≤ k ≤ Sj − 1).
  • 1 ≤ Tj ≤ N − 1 (0 ≤ j ≤ Q − 1).
  • 0 ≤ Yj,k ≤ N − 1 (0 ≤ j ≤ Q − 1, 0 ≤ k ≤ Tj − 1).
  • Xj,0, Xj,1, . . . , Xj,Sj−1, Yj,0, Yj,1, . . . , Yj,Tj−1 은 서로 다릅니다 (0 ≤ j ≤ Q − 1).
  • S0 + S1 + · · · + SQ−1 ≤ 1 000 000.
  • T0 + T1 + · · · + TQ−1 ≤ 1 000 000.

출력

각각의 질의에 대한 답을 한 줄에 하나씩 차례대로 출력합니다

예제 입력

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

출처

Contest > JOI Open Contest > JOI Open Contest 2014 1번