만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트리 컴포넌트 찾기

시간 제한1초메모리 제한1024 MB

요약
루트가 있는 트리에서 각 질의의 정점 집합을 모두 포함하는 가장 작은 연결 부분 트리의 정점 개수와 번호 합을 구합니다.
난이도

보통10점 중 6점

유형
트리, 정렬
정답자
아직 제출이 없습니다

문제

정점이 NN개이고 간선이 N−1N-1개인 트리가 주어진다. 정점 번호는 00부터 N−1N-1까지이며, 00번 정점이 루트이다. 이 트리에 대해 다음 쿼리를 QQ번 수행한다.

  • kk v1v_1 v2v_2 ... vkv_k: 정점 v1,v2,...,vkv_1, v_2, ..., v_k를 모두 포함하는 연결 컴포넌트 중 정점 수가 가장 작은 것을 CC라고 하자. CC의 정점 수와 CC에 속한 정점 번호의 총합을 공백으로 구분하여 출력한다.

입력

첫 번째 줄에 정점의 수 NN이 주어진다. (2≤N≤1000002 \le N \le 100000)

다음 N−1N-1개 줄에는 부모 정점 번호 pp와 자식 정점 번호 cc가 공백으로 구분되어 주어진다. 주어지는 그래프는 트리이다. (0≤p≤N−10 \le p \le N-1, 0≤c≤N−10 \le c \le N-1, p≠cp \ne c)

다음 줄에 쿼리의 수 QQ가 주어진다. (1≤Q≤1000001 \le Q \le 100000)

다음 QQ개 줄에는 k,v1,v2,...,vkk, v_1, v_2, ..., v_k가 공백으로 구분되어 주어진다. 모든 kk의 총합은 10610^6 이하이다. (1≤k≤N1 \le k \le N, 0≤vi≤N−10 \le v_i \le N-1 (1≤i≤k1 \le i \le k), vi≠vjv_i \ne v_j (1≤i<j≤k1 \le i < j \le k))

입력으로 주어지는 모든 수는 정수이다.

출력

쿼리마다 답을 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    7
    0 1
    0 2
    1 3
    1 4
    2 5
    2 6
    5
    1 1
    2 0 1
    2 1 2
    3 2 3 4
    7 0 1 2 3 4 5 6
    
    예상 출력
    1 1
    2 1
    3 3
    5 10
    7 21