Problem Description

Farmer John has $N$ cows numbered $1 \dots N$ ($2 \le N \le 10^5$), and the relationships between the cows can be described by a tree. Unfortunately, a disease is spreading.

Initially, some cows are infected. Each night, infected cows spread the disease to their neighbors. Once a cow is infected, she remains infected forever. After several nights, Farmer John realizes what is happening, so he tests the cows to determine which cows are infected.

You are given $Q$ ($1 \le Q \le 20$) distinct numbers of nights, each an integer in the range $[0, N]$. For each number of nights, find the minimum possible number of cows that could have been infected initially, or report that this number of nights is inconsistent with the given information.

Input Format

The first line contains an integer $N$.

The next line contains a bit string of length $N$ consisting of $1$ and $0$. A $1$ means the cow is infected, and a $0$ means the cow is still uninfected after some number of nights.

The next $N - 1$ lines describe the edges of the tree.

Then $Q$ and the $Q$ numbers of nights are given.

Output Format

Output $Q$ lines, each being the answer for the corresponding number of nights. If there is no solution, output $-1$.

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

1
1
1
1
2
5

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

10
3
2
1
1
1
1
1
1
1
1

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

3
1
1
-1
-1
-1

Hint

Sample Explanation 1

For the first four queries, one possibility is that only cow $3$ was infected initially. For the fifth query ($1$ night), one possibility is that cows $2$ and $4$ were infected initially. For the sixth query ($0$ nights), one possibility is that all five cows were infected initially.

Sample Explanation 2

For the first query ($0$ nights), one possibility is that all ten cows were infected initially. For the second query ($1$ night), one possibility is that cows $2$, $7$, and $9$ were infected initially. For the third query ($2$ nights), one possibility is that cows $2$ and $9$ were infected initially. For the fourth through the eleventh queries, one possibility is that only cow $7$ was infected initially.

Sample Explanation 3

For the first query ($0$ nights), one possibility is that cows $1$, $2$, and $3$ were infected initially. For the second query ($1$ night), one possibility is that only cow $2$ was infected initially. For the third query ($2$ nights), one possibility is that only cow $1$ was infected initially. For the fourth through the sixth queries, it is impossible to satisfy the conditions in the problem.

Testdata Properties

• Testdata $4$-$5$ satisfies $N \le 10$.
• Testdata $6$-$8$ satisfies that all cows are infected.
• Testdata $9$-$11$ satisfies $N \le 400$.
• Testdata $12$-$23$ has no additional constraints.

Translated by ChatGPT 5