Tree and Queries

Time limit3sMemory limit1024 MB

Summary

For each query, count the pairs of chosen vertices whose tree path uses only chosen vertices, given a tree with up to 250,000 vertices.

Level: Medium6 of 10
Topics: Tree, Sorting, Implementation
Solved: No attempts yet

Problem

A tree with $N$ vertices numbered from 1 to $N$ is given. The $i$ -th edge connects two distinct vertices $A_i$ and $B_i$ . ( $1 \le i \le N-1$ )

Choose some of the $N$ vertices, and let the chosen vertices be $S = \{s_1, s_2, \dots, s_K\}$ . If there is an $i$ ( $1 \le i \le K$ ) with $s_i = v$ , then vertex $v$ is said to belong to $S$ .

For two distinct vertices $u$ and $v$ that belong to $S$ , say that " $u$ and $v$ are connected on $S$ " if you can move between $u$ and $v$ along the tree using only vertices that belong to $S$ .

For example, consider the tree below. ( $N = 7$ )

If $K = 6$ and $S = \{1, 2, 3, 4, 5, 6\}$ , then " $1$ and $2$ ", " $3$ and $5$ ", and " $4$ and $6$ " are each connected on $S$ . However, " $1$ and $6$ " and " $2$ and $7$ " are not connected on $S$ .

Count the vertex pairs $(u, v)$ that satisfy all of the following conditions. This count is the connection strength of $S$ .

$u$ and $v$ are two distinct vertices.
$1 \le u < v \le N$ .
$u$ and $v$ are connected on $S$ .

Given a chosen set $S$ , write a program that computes the connection strength of $S$ . You must answer $Q$ such queries.

Input

The first line contains an integer $N$ .

Each of the next $N-1$ lines contains two integers $A_i$ and $B_i$ , describing the $i$ -th edge.

The next line contains an integer $Q$ .

Each of the next $Q$ lines describes a query: an integer $K$ , followed by $K$ integers $s_1, \dots, s_K$ .

Output

For each query, print the connection strength of the given $S$ on its own line, in order.

Constraints

$2 \le N \le 250\,000$
$1 \le Q \le 100\,000$
For every $i$ ( $1 \le i \le N-1$ ), $1 \le A_i \le N$ .
For every $i$ ( $1 \le i \le N-1$ ), $1 \le B_i \le N$ .
For every $i$ ( $1 \le i \le N-1$ ), $A_i \ne B_i$ .
The given graph is a tree.
For every query, $1 \le K \le N$ .
In each query, for every $i$ ( $1 \le i \le K$ ), $1 \le s_i \le N$ .
In each query, the $K$ chosen vertices $s_1, \dots, s_K$ are distinct.
The sum of $K$ over all $Q$ queries is at most $1\,000\,000$ .

Examples1

Example 1

Input

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

Expected output