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