Дистанционный практикум по программированию

В стране Триландии близятся выборы новых столиц. Столицы в Триландии необычные, поскольку ими являются одновременно сразу три различных города. Такая идея размещения столиц основана на исследованиях эффективности управления страной, выполненных ведущими экономистами Триландии.

Всего в Триландии n городов, из которых некоторые пары городов соединены дорогами и по каждой из них можно проехать в обе стороны. Время проезда по каждой дороге в одну сторону равно одному часу. При этом все города соединены дорогами таким образом, что из каждого города можно добраться в любой другой, причем это можно сделать единственным способом, если по каждой дороге проезжать не более одного раза и только в одну сторону.

Как показали результаты проведенных триландскими экономистами исследований, управление страной будет наиболее эффективным, если три столицы будут выбраны так, что время проезда по кратчайшему пути между каждой парой столиц составит ровно d часов. Перед проведением выборов необходимо знать, сколько существует различных троек городов, удовлетворяющих описанным выше свойствам. Две тройки городов считаются различными, если в первой тройке есть хотя бы один город, которого нет во второй тройке, и наоборот.

Требуется написать программу, которая по количеству городов в Триландии и описанию дорог находит количество троек городов, которые могут быть столицами.

Формат входного файла

Первая строка входного файла содержит два разделенных пробелом целых числа: количество городов в Триландии n и требуемое время в пути между столицами d (3 ≤ n ≤ 10⁵, 1 ≤ d < n). Каждая из последующих (n – 1) строк содержит описание одной дороги: пару разделенных пробелом различных целых чисел a_i и b_i — номера городов, которые соединены двусторонней дорогой (1 ≤ a_i ≤ n, 1 ≤ b_i ≤ n, a_i ≠ b_i). Каждая пара городов соединена не более чем одной дорогой.

Формат выходного файла

Выходной файл должен содержать одно целое число — количество подходящих троек городов, которые могут быть выбраны столицами. В случае, если подходящих троек городов не окажется, выходной файл должен содержать ноль.

Примеры входных и выходных файлов

Входные данные	Выходные данные
4 2 1 2 1 3 1 4	1
7 2 1 2 1 3 1 4 5 1 5 6 5 7	5

Пояснения к примерам

В первом примере существует единственный способ выбрать три столицы: города с номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.

Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.

 

Разбор задачи (из комплекта методических материалов). На наш взгляд, в конце написано не очень понятно

Видеоразбор всех задач олимпиады можно найти на сайте www.100ege.ru На нём нужно зарегистрироваться в качестве школьника и в личный кабинет добавить курс "Программирование (продвинутый уровень)"