Did you know that the universe is actually in a rooted tree? Well maybe not, but that is certainly true in Gug's universe. In other words, there are N planets in Gug's universe, with N-1 bidirectional edges bettween planets so that there is exactly 1 path between any two planets via the edges. Each edge i connects planet Xi and Yi.
Gug's house is at planet 1. Gug thinks he is the center of the universe so the tree will be rooted at planet 1. In gug's universe, leaf planets contain restaurants. A rooted tree is a tree with a special vertex called root. In a rooted tree among any two vertices connected by an edge, one vertex is a parent (the one closer to the root), and the other one is a child. A vertex is called a leaf, if it has no children.
Gug wants to visit the restaurants in his universe. Unfortunately for Gug, some planets have cats, while some do not. Gug does not like cats, so he will not go to a restaurant if the direct path from his house to that restaurant passes through more than K planets with cats consecutively. Gug wants to know how many restaurants he will be able to visit.
The first line of input will contain 2 integers, N, K- the number of planets of the tree and the maximum number of consecutive planets with cats that is still ok for Gug.
The second line contains N integers A1, A2, ..., An, where each Ai either equals to 0 (then vertex i has no cat), or equals to 1 (then vertex i has a cat).
The next N-1 lines of input will contain two integers each, Xi, Yi- the edges in Gug's universe.
The output should contain one integer representing the number of restaurants Gug can visit.
For all subtasks: 1 ≤ Xi, Yi ≤ N, 0 ≤ Ai ≤ 1
Subtask 1 (49%): 1 ≤ N ≤ 105, K = 1.
Subtask 2 (51%): 1 ≤ N ≤ 105.
Subtask 3 (0%): Sample Testcases.
4 1 1 1 0 0 1 2 1 3 1 4
2
7 1 1 0 1 1 0 0 0 1 2 1 3 2 4 2 5 3 6 3 7
2
| Subtask | Score |
|---|---|
| 1 | 49 |
| 2 | 51 |
| 3 | 0 |