33159번 - 트리핑

문제

$N$개의 노드로 이루어진 트리가 주어질 때 다음 쿼리를 $Q$개 처리해 보자.

• $k ,円 u_1 ,円 u_2 ,円 \dots ,円 u_k$: 트리에서 임의의 노드를 선택한 다음, 선택한 노드와 $u_1, u_2, \dots, u_k$번 노드들과의 거리의 합의 최솟값을 출력한다.

입력

첫 번째 줄에 트리의 노드 개수 $N,ドル 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 300,000円;1 \le Q \le 500,円 000)$

두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선을 이루는 서로 다른 두 노드의 번호 $a,ドル $b$가 공백으로 구분되어 주어진다. $(1\le a, b \le N)$

다음 $Q$개의 줄에 걸쳐 쿼리 $k ,円 u_1 ,円 u_2 ,円 \dots u_k$가 주어진다. $(1 \le k \le N$; 1ドル \le u_i \le N$; $i \ne j \implies u_i \ne u_j)$

모든 쿼리에 대하여 $k$의 합은 500ドル,円 000$ 이하이다.

출력

각 쿼리마다 주어진 노드들과 선택한 노드 사이 거리 합의 최솟값을 $Q$개의 줄에 걸쳐 하나씩 출력한다.

제한

힌트