트리와 쿼리

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

$N$개의 정점 중 몇 개를 골라, 그 고른 정점들을 $S = \\{s\_1, s\_2, \dots , s\_K\\}$라고 하자. 또한, $s\_i = v$를 만족하는 $i$ ($1 ≤ i ≤ 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$의 연결 강도라고 하자.

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

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

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

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

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

다음 $Q$개의 줄에 각 질의에 대한 정보가 주어진다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄은 $i$번째 질의를 나타내며, 정수 $K$와 $K$개의 정수 $s\_1, \dots , s\_K$가 차례대로 주어진다.

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

• $2 ≤ N ≤ 250\\,000$
• $1 ≤ Q ≤ 100\\,000$
• 모든 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $1 ≤ A\_i ≤ N$.
• 모든 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $1 ≤ B\_i ≤ N$.
• 모든 $i$ ($1 ≤ i ≤ N - 1$)에 대해, $A\_i ≠ B\_i$.
• 주어지는 그래프는 트리이다.
• 모든 질의에 대해, $1 ≤ K ≤ N$.
• 각 질의에서, 모든 $i$ ($1 ≤ i ≤ K$)에 대해, $1 ≤ s\_i ≤ N$.
• 각 질의에서, 고른 $K$개의 정점 $s\_1, \dots , s\_K$는 서로 다르다.
• $Q$개의 질의에서 주어지는 $K$들의 합은 $1\\,000\\,000$ 이하이다.