- All Contests
- HourRank 20
- Birjik and Nicole's Tree Game

# Birjik and Nicole's Tree Game

# Birjik and Nicole's Tree Game

Nicole and Birjik are seniors taking a break from job applications by creating the following game:

- Birjik draws a
*rooted tree*with vertices numbered from to , rooted at vertex . - Nicole creates queries. For each query, she takes a copy of the tree and colors of its vertices
*black*, leaving the remaining vertices*white*. - The goal of the game is to answer each query by finding the respective values of , where each is the number of subtrees containing exactly
*black*vertices (including the subtree's root vertex).

For example, the diagram below depicts a query on a tree where and the *black* vertices are , , and :

Given the tree and queries, solve each query by printing the values of on a new line.

**Input Format**

The first line contains an integer, , denoting the number of vertices of the tree.

Each of the subsequent lines contains two space-separated integers, and , describing an edge connecting vertices and .

The next line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

- The first line contains an integer denoting .
- The second line contains space-separated integers describing the respective IDs of the vertices to color
*black*.

**Constraints**

- It is guaranteed that the given graph is a tree.
- It is guaranteed that the vertex IDs given in each query are distinct IDs that exist in the tree.
- The sum of over all queries in a test case is

**Output Format**

For each query, print a single line containing integers describing the respective values of . Recall that each is the total number of subtrees containing exactly *black* vertices.

**Sample Input 0**

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

**Sample Output 0**

```
2 3 1 1
1 4 1 1
```

**Explanation 0**

In this example, the graph and queries look like this:

We perform the following queries:

Color vertices , , and black:

We then print the respective values of as

`2 3 1 1`

on a new line.Color vertices , , and black:

We then print the respective values of as

`1 4 1 1`

on a new line.

**Sample Input 1**

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

**Sample Output 1**

```
3 3 0 1
1 4 1 0 1
5 1 1
```

**Explanation 1**

In this example, the graph and queries look like this:

Follow the same process as *Sample Case 0* to verify the *Expected Output* values.