트리 안의 트리

시간 제한6초메모리 제한512 MB

요약
각 정점 부분집합의 최소 연결 부분 트리에 속한 변의 수를 오일러 순회 번호와 LCA로 구합니다.
난이도

어려움10점 중 8점

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

문제

트리가 주어진다. 트리는 정점 nn개와 간선 n−1n-1개로 이루어진, 방향이 없고 연결된 그래프다. 정점은 1,2,…,n1, 2, \ldots, n으로 번호가 매겨져 있다.

qq개의 질의가 주어진다. 각 질의마다 트리의 정점 부분집합 P={v1,v2,…,vk}P = \{v_1, v_2, \ldots, v_k\}를 고르고, PP의 최소 신장 트리에 간선이 몇 개 있는지 묻는다. 다시 말해, PP에 속한 두 정점 사이의 경로 중 적어도 하나에 포함되는 간선의 수를 묻는다. 모든 질의의 답을 구하라.

입력

첫째 줄에는 트리의 정점 수인 자연수 nn이 주어진다. (2≤n≤1 000 0002 \le n \le 1\,000\,000)

다음 n−1n-1개 줄에는 서로 다른 두 자연수 a,ba, b가 주어지며, 이는 정점 aa와 bb가 간선으로 연결되어 있음을 뜻한다. (1≤a,b≤n1 \le a, b \le n)

그다음 줄에는 질의의 수인 자연수 qq가 주어진다. (1≤q≤60 0001 \le q \le 60\,000)

다음 qq개 줄에는 각각 자연수 kk가 먼저 주어지고, 이어서 11과 nn 사이의 서로 다른 자연수 kk개가 주어진다. 이는 질의에서 다루는 집합의 정점들이다. (k≥2k \ge 2)

모든 질의의 kk 값의 합은 300 000300\,000 이하다.

출력

각 질의마다 구한 간선 수를 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    5
1 2
2 3
3 4
4 5
4
2 1 2
2 3 5
2 1 5
3 1 3 5
    예상 출력
    1
2
4
4

  2. 예제 2

    입력
    10
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
5
2 4 5
3 4 5 6
4 2 4 7 10
4 4 5 9 10
9 1 2 3 5 6 7 8 9 10
    예상 출력
    2
5
7
9
8