infO(1)Cup 2025 Day 2 - Mirror | Radio

Task

Consider a network of $N$ radios, linked together by $N-1$ communication channels. We model the radios and the communication channels as a tree. Each radio can be in one of three states: without signal (NS), with signal (S), or deactivated (D). Once a radio is in state S or D, it stays in that state permanently - on the other hand a radio in state NS can still change state.

Every day the following occurs simultaneously: every radio in state S will attempt to transmit to every other radio to which it is directly linked by a communication channel. Consider any radio $r$ in state NS, and suppose it received $t$ transmissions today. If $t = 0$, then $r$ remains in state NS tomorrow. If $t = 1$, then $r$ enters state S permanently starting tomorrow. If $t \gt 1$, then $r$ enters state D permanently starting tomorrow.

Note that no matter the current state of the network, there will eventually be a day from which no radio ever changes state again. Call this final state of the network the stable state.

Little Steve has $Q$ queries of the form:

Suppose $M$ radios $x_1, \dots, x_M$ are initially in state S, and all other radios are in state NS. How many radios will be in state S when the network reaches its stable state?

Can you answer Little Steve's queries?

Input data

The first line of the input contains $N$. The next $N - 1$ lines contain pairs $(x, y)$, which denote the communication channels between the radios. The next line contains $Q$. The next $Q$ lines encode the queries. Each line contains $M$ followed by $x_1, \dots, x_M$.

Output data

Output the answers to the queries, each on a different line.

Constraints and clarifications

• Each query is independent.
• $N \leq 200 \ 000$;
• $Q \leq 30 \ 000$;
• Let $\sum M$ denote the sum of $M$ over all queries in the input.
• $\sum M \leq 300 \ 000$.

Example 1

stdin

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

stdout

4
5
5
6
2

Explanation

In the following drawing, an uncoloured vertex is in state NS, a $\textcolor{green}{green}$ vertex is in state S and a $\textcolor{pink}{pink}$ vertex is in state D.

The tree in this example is

First query. In this case, the tree undergoes the following sequence of states:

So the answer is $4$, due to vertices $2, 4, 5, 6$.

Second query. The tree undergoes the following sequence of states:

So the answer is $5$, due to vertices $1, 3, 4, 5, 6$.

Third query. The tree undergoes the following sequence of states:

So the answer is $5$, due to vertices $1, 3, 4, 5, 6$.

Fourth query. The tree undergoes the following sequence of states:

So the answer is $6$, due to vertices $1, 2, 3, 4, 5, 6$.

Fifth query. The tree undergoes the following sequence of states:

So the answer is $2$, due to vertices $4, 6$.

Example 2

stdin

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

stdout

7
6
6

Explanation

The tree in this example is

First query. The tree undergoes the following sequence of states:

So the answer is $7$, due to vertices $1, 2, 3, 4, 5, 6, 7$.

Second query. The tree undergoes the following sequence of states:

So the answer is $6$, due to vertices $1, 2, 4, 5, 6, 7$.

Third query. The tree undergoes the following sequence of states:

So the answer is $6$, due to vertices $1, 2, 3, 5, 6, 7$.

Example 3

stdin

15
1 2
2 3
2 4
2 5
1 6
3 7
2 8
2 9
3 10
3 11
11 12
10 13
13 14
13 15
15
13 3 6 9 2 11 8 5 14 13 15 10 4 1
10 8 9 5 11 2 10 6 12 15 4
11 6 13 4 12 9 11 7 2 3 15 5
11 14 2 15 6 7 12 9 8 3 10 4
2 4 5
10 2 5 7 10 8 15 9 1 14 3
6 14 1 12 15 10 2
3 3 11 15
10 15 3 8 4 6 5 2 11 14 9
4 5 9 4 7
11 12 5 2 3 14 8 7 4 6 1 11
12 8 13 11 3 4 9 7 1 10 2 12 14
4 10 9 6 5
8 7 1 8 5 12 10 15 4
5 11 3 14 10 6

stdout

15
10
13
12
2
14
12
15
13
11
15
15
12
10
13