트리와 쿼리

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

요약

트리와 여러 개의 정점 집합 S가 주어질 때, 경로 위의 정점이 모두 S에 속하는 정점 쌍의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 트리, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

정점이 $1$ 부터 $N$ 까지 $N$ 개인 트리가 주어진다. $i$ 번째 간선은 서로 다른 두 정점 $A_i$ , $B_i$ 를 잇는다. ( $1 \le i \le N-1$ )

$N$ 개의 정점 중 몇 개를 골라, 고른 정점들의 집합을 $S = \{s_1, s_2, \dots, s_K\}$ 라고 하자. $s_i = v$ 를 만족하는 $i$ ( $1 \le i \le K$ )가 있으면, 정점 $v$ 가 $S$ 에 속한다고 한다.

$S$ 에 속하는 서로 다른 두 정점 $u$ , $v$ 에 대하여, $S$ 에 속한 정점만 지나서 트리 위에서 $u$ 와 $v$ 사이를 오갈 수 있으면, " $u$ 와 $v$ 는 $S$ 위에서 연결되어 있다"고 한다.

예를 들어, 아래와 같은 트리를 보자. ( $N = 7$ )

$K = 6$ 이고 $S = \{1, 2, 3, 4, 5, 6\}$ 이면, " $1$ 과 $2$ ", " $3$ 과 $5$ ", " $4$ 와 $6$ "은 각각 $S$ 위에서 연결되어 있다. 그러나 " $1$ 과 $6$ ", " $2$ 와 $7$ "은 $S$ 위에서 연결되어 있지 않다.

다음 조건을 모두 만족하는 정점 쌍 $(u, v)$ 의 개수를 $S$ 의 연결 강도라고 한다.

$u$ 와 $v$ 는 서로 다른 두 정점이다.
$1 \le u < v \le N$ 이다.
$u$ 와 $v$ 는 $S$ 위에서 연결되어 있다.

고른 정점 집합 $S$ 가 주어질 때, $S$ 의 연결 강도를 계산하는 프로그램을 작성하라. 이러한 질의 $Q$ 개에 모두 답해야 한다.

입력

첫 번째 줄에 정수 $N$ 이 주어진다.

다음 $N-1$ 개의 줄에 각 간선의 정보가 주어진다. $i$ 번째 줄에는 두 정수 $A_i$ , $B_i$ 가 주어진다.

다음 줄에 정수 $Q$ 가 주어진다.

다음 $Q$ 개의 줄에 각 질의가 주어진다. 각 줄은 정수 $K$ 와 이어서 $K$ 개의 정수 $s_1, \dots, s_K$ 로 이루어진다.

출력

$Q$ 개의 줄에 걸쳐 각 질의의 답을 순서대로 출력한다. $i$ 번째 줄에는 $i$ 번째 질의에서 주어진 $S$ 의 연결 강도를 출력한다.

제한

$2 \le N \le 250\,000$
$1 \le Q \le 100\,000$
모든 $i$ ( $1 \le i \le N-1$ )에 대해, $1 \le A_i \le N$ .
모든 $i$ ( $1 \le i \le N-1$ )에 대해, $1 \le B_i \le N$ .
모든 $i$ ( $1 \le i \le N-1$ )에 대해, $A_i \ne B_i$ .
주어지는 그래프는 트리이다.
모든 질의에 대해, $1 \le K \le N$ .
각 질의에서 모든 $i$ ( $1 \le i \le K$ )에 대해, $1 \le s_i \le N$ .
각 질의에서 고른 $K$ 개의 정점 $s_1, \dots, s_K$ 는 서로 다르다.
$Q$ 개의 질의에서 주어지는 $K$ 의 합은 $1\,000\,000$ 이하이다.

예제1

예제 1

입력

7
1 2
1 3
1 5
2 7
4 6
4 7
6
1 1
2 1 2
4 1 2 3 4
5 1 2 4 6 7
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7

예상 출력