eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расстояние в дереве

Расстояние в дереве

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Деревом называется связный граф, не содержащий циклов.

Расстоянием между двумя вершинами дерева называется длина (в ребрах) кратчайшего пути между этими вершинами.

Дано дерево из n вершин и положительное число k. Посчитайте количество различных пар вершин дерева, расстояние между которыми равно k. Обратите внимание, что пары (v, u) и (u, v) считаются одной и той же парой.

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

В первой строке записаны два целых числа n и k\:(1 \le n \le 50000, 1 \le k \le 500) — количество вершин дерева и требуемое расстояние между вершинами.

В следующих n - 1 строках записаны ребра дерева в формате a_i\:b_i\:(1 \le a_i, b_i \le n, a_i \neq b_i), где a_i и b_i — вершины дерева, соединенные i-ым ребром. Все заданные ребра различны.

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

Выведите единственное целое число — количество различных пар вершин дерева, расстояние между которыми равно k.

Пример

Входные данные #1
5 2
1 2
2 3
3 4
2 5
Выходные данные #1
4
Источник VK Cup 2012 Раунд 1, Задача D