트리와 쿼리

문제

$11$부터 $NN$까지 $NN$개의 정점으로 이루어진 트리가 있다. $ii$번째 간선은 서로 다른 두 정점 $A_{i}A\_i$, $B_{i}B\_i$를 잇는다. (1 ≤ i ≤ N - 1)

$NN$개의 정점 중 몇 개를 골라, 그 고른 정점들을 $S=\{s_1,s_2,\dots ,s_K\}S\; =\; \backslash \{s\_1,\; s\_2,\; \backslash dots\; ,\; s\_K\backslash \}$라고 하자. 또한, $s_i=vs\_i\; =\; v$를 만족하는 $ii$ (1 ≤ i ≤ K)가 존재할 때, 정점 $vv$가 $SS$에 속한다고 부르자.

$SS$에 속하는 서로 다른 두 정점 $uu$, $vv$에 대하여, $SS$에 속하는 정점만을 이용하여 트리 위에서 $uu$, $vv$ 사이를 오갈 수 있다면, “$uu$와 $vv$는 $SS$ 위에서 연결되어 있다”고 하자.

예를 들어, 아래와 같은 트리를 생각하자. ($N=7N\; =\; 7$)

만일, $K=6K\; =\; 6$, $S=\{1,2,3,4,5,6\}S\; =\; \backslash \{1,\; 2,\; 3,\; 4,\; 5,\; 6\backslash \}$라면, “$11$과 $22$”, “$33$과 $55$”, “$44$와 $66$”은 각각 서로 $SS$ 위에서 연결되어 있다. 그러나, “$11$과 $66$”, “$22$와 $77$”은 각각 서로 $SS$ 위에서 연결되어 있지 않다.

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

1. $uu$와 $vv$는 서로 다른 두 정점.
2. 1 &le; u < v &le; N.
3. $uu$와 $vv$는 $SS$ 위에서 연결되어 있다.

고른 정점들 $SS$가 주어질 때, $SS$의 연결 강도를 계산하는 프로그램을 작성하라. 여러분은 이러한 질의 $QQ$개에 대하여 모두 답해야 한다.

입력

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

다음 ($N-1N\; -\; 1$)개의 줄에 각 간선에 대한 정보가 주어진다. 이 중 $ii$ (1 &le; i &le; N - 1)번째 줄에는 두 정수 $A_{i}A\_i$, $B_{i}B\_i$가 주어진다.

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

다음 $QQ$개의 줄에 각 질의에 대한 정보가 주어진다. 이 중 $ii$ (1 &le; i &le; Q)번째 줄은 $ii$번째 질의를 나타내며, 정수 $KK$와 $KK$개의 정수 $s_1,\dots ,s_{K}s\_1,\; \backslash dots\; ,\; s\_K$가 차례대로 주어진다.

출력

첫 번째 줄부터 $QQ$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $ii$ (1 &le; i &le; Q)번째 줄에는 $ii$번째 질의에서 주어진 $SS$에 대하여, $SS$의 연결 강도를 출력한다.

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

0
1
3
10
7
21