Расстояние в дереве
Расстояние в дереве
Деревом называется связный граф, не содержащий циклов.
Расстоянием между двумя вершинами дерева называется длина (в ребрах) кратчайшего пути между этими вершинами.
Дано дерево из 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.
Пример
5 2 1 2 2 3 3 4 2 5
4