Cow Disease Propagation

Farmer John has N cows numbered from \(1\) to \(N\). The cows are connected by \(N-1\) edges forming a tree structure. A contagious disease is spreading among the cows. Initially, an unknown set of cows (the initially infected set) are infected. Every night, each infected cow transmits the disease to all of its neighbors. Once a cow is infected, it remains infected forever. After some nights the infection has spread, and Farmer John performs tests that reveal for each cow whether it is infected or not.

You are given the tree structure, the final infection status of each cow and \(Q\) queries. Each query gives a nonnegative integer \(t\) (with \(0 \le t \le N\)) representing the number of nights that have passed before testing. For each query, determine the minimum possible size of the initially infected set which could have produced the observed infection pattern after \(t\) nights; or report that the information is inconsistent (i.e. no choice of initial infections could have led to the given pattern).

The disease transmission obeys the following rule: if a cow was infected initially, after \(t\) nights the set of infected cows will equal the union of all \(t\)-neighborhoods of the initially infected cows, i.e. a cow \(v\) is infected if and only if there exists an initially infected cow \(u\) with \(d(u,v)\le t\) where \(d(u,v)\) denotes the distance in the tree. Furthermore, if \(t>0\) then no uninfected cow can lie within distance \(t\) of any initially infected cow. (When \(t=0\), the infection does not spread, and the initially infected set must exactly match the observed infected cows.)

It is guaranteed that \(2\le N\le 10^5\) and \(1\le Q\le 20\). The input format is described below.

---

Input Format

• The first line contains two integers \(N\) and \(Q\).
• The next \(N-1\) lines each contain two integers \(u\) and \(v\), indicating an edge between cows \(u\) and \(v\).
• The next line contains a string of \(N\) characters (each either '0' or '1') with no spaces. The \(i\)th character is '1' if cow \(i\) is infected in the test results, and '0' otherwise.
• The next \(Q\) lines each contain an integer \(t\) (\(0\le t\le N\)).

---

Output Format

• For each query, output a single line containing the minimum number of cows that could have been initially infected to yield the given final infection pattern after \(t\) nights, or output -1 if the information is inconsistent.

---

Note on the Problem: For any query with \(t=0\), since no spread occurs, the final infection pattern must coincide with the set of initially infected cows, so the answer is simply the number of infected cows. For \(t>0\), an initially infected cow must be chosen from the set of infected cows that are sufficiently far away from any uninfected cow (specifically, a cow \(v\) can only be chosen as an initially infected cow if the distance from \(v\) to the nearest uninfected cow is greater than \(t\); this ensures that the infection will not reach a cow that is known to be uninfected). Using this observation, one may first precompute for each cow \(v\) the distance \(d(v)\) to the nearest uninfected cow (by multi‐source BFS), and then use a greedy strategy (with binary lifting on the DFS tree) to cover the final infected set with \(t\)-neighborhoods of the chosen initially infected cows. If at any stage an infected cow cannot be covered, the answer is \(-1\).

---

Constraints: \(2\le N\le 10^5,\ 1\le Q\le 20\).

inputFormat

The input begins with a line containing two integers \(N\) and \(Q\). The next \(N-1\) lines each contain two integers \(u\) and \(v\), describing an edge of the tree. The following line contains a string of exactly \(N\) characters ('0' or '1') with no spaces, representing the infection status of cows \(1\) through \(N\). Then \(Q\) lines follow, each containing a single integer \(t\) (with \(0\le t\le N\)).

outputFormat

For each query, output a single integer on its own line: the minimum number of cows that could have been initially infected to yield the final infection state after \(t\) nights, or \(-1\) if the information is inconsistent.

sample

5 2
1 2
2 3
2 4
1 5
11011
1
2

-1
-1

</p>