Кефа решил отпраздновать свой первый крупный заработок походом в ресторан.
Он живет возле необычного парка. Парк представляет из себя подвешенное дерево из n вершин c корнем в вершине 1. В вершине 1 также находится дом Кефы. К сожалению для нашего героя, в парке также находятся коты. Кефа уже выяснил номера вершин, в которых находятся коты.
В листовых вершинах парка находятся рестораны. Кефа хочет выбрать ресторан, в который он пойдет, но, к сожалению, он очень боится котов, поэтому он ни за что не пойдёт в ресторан, на пути к которому от его дома найдётся более m подряд идущих вершин с котами.
Ваша задача — помочь Кефе посчитать количество ресторанов, в которые он может сходить.
В первой строке записаны два целых числа n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ n) — количество вершин дерева и максимальное количество подряд идущих вершин с котами, которое способен перенести Кефа.
Во второй строке содержится n целых чисел a1, a2, ..., an, где каждое ai либо равняется 0 (тогда в вершине i нет кота), либо равняется 1 (тогда в вершине i есть кот).
В следующих n - 1 строках записаны ребра дерева в формате «xi yi»(без кавычек) (1 ≤ xi, yi ≤ n, xi ≠ yi), где xi и yi — вершины дерева, соединенные очередным ребром.
Гарантируется, что данный набор рёбер задаёт дерево.
Одно целое число — количество различных листьев дерева, на пути от дома Кефы до которых не больше m подряд идущих вершин с котами.
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
Напомним, что дерево — это связный граф на n вершинах, состоящий из n - 1 ребра. Подвешенное дерево — это дерево с особой выделенной вершиной, корнем. В подвешенном дереве из любых двух вершин, соединённых ребром, одна называется предком (та из них, что ближе к корню), а оставшаяся — ребёнком. Вершина называется листом, если у неё нет детей.
Пояснение к первому тесту из условия: 
Красным цветом отмечены вершины в которых находятся коты. Рестораны находятся в вершинах 2, 3, 4. Кефа не может сходить только в ресторан, находящийся в вершине 2.
Пояснение ко второму тесту из условия: 
Рестораны находятся в вершинах 4, 5, 6, 7. Кефа не может попасть в рестораны 6, 7.
| Codeforces Round 321 (Div. 2) |
|---|
| Закончено |
