09. Кефа и парк#

📝 Условие#

Парк — дерево с корнем в 1, в некоторых вершинах живут коты. Сколько листьев-ресторанов можно достичь, если на пути нельзя встретить больше m котов подряд?

📥 Входные данные#

В первой строке два числа n и m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ n). Во второй — n чисел 0/1: есть ли кот в вершине. Далее n − 1 строк — рёбра дерева x y. Корень — вершина 1.

📤 Выходные данные#

Одно число — количество подходящих листьев.

🧪 Тесты#

Тест 1#

Ввод:

4 1
1 1 0 0
1 2
1 3
1 4

Вывод:

2

Тест 2#

Ввод:

7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

Вывод:

2

Тест 3#

Ввод:

5 2
1 1 0 1 1
1 2
2 3
3 4
4 5

Вывод:

1

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня