cho.sh

공장들

가중 트리에서 쿼리마다 주어지는 두 공장 집합 사이 최단 거리를 구합니다.

어려움9분할 정복트리최단 경로아직 제출이 없습니다시간 제한6초메모리 제한512 MB

문제

IOI 왕국에는 00번부터 N−1N-1번까지 번호가 붙은 도시가 NN개 있다. 도시는 양방향으로 통행할 수 있는 도로 N−1N-1개로 이어져 있고, 어느 두 도시 사이든 도로를 몇 개 지나 오갈 수 있다.

IOI 왕국에는 특별한 제품을 만드는 회사가 많다. 회사마다 제품을 한 종류만 만들고, 서로 다른 두 회사가 같은 종류의 제품을 만드는 일은 없다. 회사는 저마다 공장을 하나 이상 두고 있으며, 공장은 모두 도시 중 한 곳에 지어져 있다. 한 도시에 여러 회사가 공장을 둘 수도 있다.

회사 CAC_A가 회사 CBC_B의 제품을 필요로 할 때가 있다 (CA≠CBC_A \ne C_B). 이때는 CBC_B의 공장 하나에서 CAC_A의 공장 하나로 제품을 옮기면 된다. 두 회사는 공장 사이의 거리가 가장 짧아지도록 공장을 고른다.

먼저 도시의 수와 도로 정보가 주어지고, 이어서 질의가 QQ개 주어진다. jj번 질의의 뜻은 이렇다. 도시 Xj,0,…,Xj,Sj−1X_{j,0}, \dots, X_{j,S_j-1}에 공장을 둔 회사 UjU_j가 도시 Yj,0,…,Yj,Tj−1Y_{j,0}, \dots, Y_{j,T_j-1}에 공장을 둔 회사 VjV_j의 제품을 필요로 한다. 질의마다 제품을 옮기는 데 드는 최소 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 NN과 QQ가 공백을 사이에 두고 주어진다. IOI 왕국에 도시가 NN개 있고, 질의가 QQ개 주어진다는 뜻이다.

이어지는 N−1N-1개 줄 가운데 i+1i+1번째 줄 (0≤i≤N−20 \le i \le N-2)에는 정수 AiA_i, BiB_i, DiD_i가 공백을 사이에 두고 주어진다. 도시 AiA_i와 도시 BiB_i를 잇는 길이 DiD_i짜리 도로가 있다는 뜻이다.

그다음 3Q3Q개 줄에 질의가 주어진다. jj번 질의 (0≤j≤Q−10 \le j \le Q-1)의 정보는 3j+13j+1번째 줄부터 3j+33j+3번째 줄까지다.

3j+13j+1번째 줄에는 정수 SjS_j와 TjT_j가 공백을 사이에 두고 주어진다. 회사 UjU_j가 도시 SjS_j곳에, 회사 VjV_j가 도시 TjT_j곳에 공장을 두었다는 뜻이다.

3j+23j+2번째 줄에는 정수 SjS_j개 Xj,0,…,Xj,Sj−1X_{j,0}, \dots, X_{j,S_j-1}이 공백을 사이에 두고 주어진다. 회사 UjU_j가 이 도시들에 공장을 두었다는 뜻이다.

3j+33j+3번째 줄에는 정수 TjT_j개 Yj,0,…,Yj,Tj−1Y_{j,0}, \dots, Y_{j,T_j-1}이 공백을 사이에 두고 주어진다. 회사 VjV_j가 이 도시들에 공장을 두었다는 뜻이다.

모든 입력은 다음 조건을 만족한다.

  • 2≤N≤500 0002 \le N \le 500\,000
  • 1≤Q≤100 0001 \le Q \le 100\,000
  • 0≤Ai≤N−10 \le A_i \le N-1, 0≤Bi≤N−10 \le B_i \le N-1, Ai≠BiA_i \ne B_i (0≤i≤N−20 \le i \le N-2)
  • 1≤Di≤100 000 0001 \le D_i \le 100\,000\,000 (0≤i≤N−20 \le i \le N-2)
  • 도로를 따라 어느 도시에서든 나머지 모든 도시로 갈 수 있다.
  • 1≤Sj≤N−11 \le S_j \le N-1, 1≤Tj≤N−11 \le T_j \le N-1 (0≤j≤Q−10 \le j \le Q-1)
  • 0≤Xj,k≤N−10 \le X_{j,k} \le N-1 (0≤k≤Sj−10 \le k \le S_j-1), 0≤Yj,k≤N−10 \le Y_{j,k} \le N-1 (0≤k≤Tj−10 \le k \le T_j-1)
  • 한 질의에 나오는 Xj,0,…,Xj,Sj−1,Yj,0,…,Yj,Tj−1X_{j,0}, \dots, X_{j,S_j-1}, Y_{j,0}, \dots, Y_{j,T_j-1}은 모두 서로 다르다.
  • S0+S1+⋯+SQ−1≤1 000 000S_0 + S_1 + \dots + S_{Q-1} \le 1\,000\,000
  • T0+T1+⋯+TQ−1≤1 000 000T_0 + T_1 + \dots + T_{Q-1} \le 1\,000\,000

출력

질의의 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

힌트

예제의 세 질의는 다음과 같이 풀린다.

  • 0번 질의에서 회사 U0U_0는 도시 0번과 6번에, 회사 V0V_0는 도시 3번과 4번에 공장을 두었다. 도시 3번의 V0V_0 공장에서 도시 6번의 U0U_0 공장까지가 가장 가깝고, 그 거리는 12이다.
  • 1번 질의에서 회사 U1U_1은 도시 0번, 1번, 3번에, 회사 V1V_1은 도시 4번과 6번에 공장을 두었다. 도시 6번의 V1V_1 공장에서 도시 1번의 U1U_1 공장까지가 가장 가깝고, 그 거리는 3이다.
  • 2번 질의에서 회사 U2U_2는 도시 2번에, 회사 V2V_2는 도시 5번에 공장을 두었다. 도시 5번의 V2V_2 공장에서 도시 2번의 U2U_2 공장까지의 거리는 11이다.