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$개의 줄에 걸쳐 하나씩 출력한다.