Cowntact Tracing

문제

Farmer John has $NN$ ($2\le N\le {10}^{5}2\backslash le\; N\backslash le\; 10^5$) cows labeled $1\dots N1\backslash dots\; N$, where the connections between cows are described by a tree. Unfortunately, there is a sickness spreading throughout.

Initially, some cows start off infected. Every night, an infected cow spreads the sickness to their neighbors. Once a cow is infected, she stays infected. After some amount of nights, Farmer John realizes that there is an issue so he tests his cows to determine who has the sickness.

You are given $QQ$ ($1\le Q\le 201\backslash le\; Q\backslash le\; 20$) different values for the number of nights, each an integer in the range $[0,N][0,N]$. For each number of nights, determine the minimum number of cows that could have started with the illness, or that the number of nights is inconsistent with the given information.

입력

The first line contains $NN$.

The next line contains a bit string of length $NN$, where the $ii$th bit is 1 if the $ii$th cow is infected and 0 otherwise. At least one cow is infected.

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

Then $QQ$, followed by the $QQ$ values for the number of nights.

출력

$QQ$ lines, the answers for each number of nights, or $-1-1$ if impossible.

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