e-olymp
Соревнования

Dynamic programming on Trees - Top Level

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

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

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

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

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

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

В следующих n - 1 строках записаны ребра дерева в формате ai bi (1 ≤ ai, bi ≤ n, ai ≠ bi), где ai и bi - вершины дерева, соединенные i-ым ребром. Все заданные ребра различны.

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

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

Лимит времени 1 секунда
Лимит использования памяти 244.24 MiB
Входные данные #1
5 2
1 2
2 3
3 4
2 5
Выходные данные #1
4
Источник VK Cup 2012 Раунд 1, Задача D