Задача H. Столицы ≡
| Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 2 сек | |
| Входной файл: | capitals.in | Ограничение памяти: | 512 Мб | |
| Выходной файл: | capitals.out | |||
| Максимальный балл: | 102 |
Условие
В стране Триландии близятся выборы новых столиц. Столицы в Триландии необычные, поскольку ими являются одновременно сразу три различных города. Такая идея размещения столиц основана на исследованиях эффективности управления страной, выполненных ведущими экономистами Триландии.
Всего в Триландии n городов, из которых некоторые пары городов соединены дорогами и по каждой из них можно проехать в обе стороны. Время проезда по каждой дороге в одну сторону равно одному часу. При этом все города соединены дорогами таким образом, что из каждого города можно добраться в любой другой, причем это можно сделать единственным способом, если по каждой дороге проезжать не более одного раза и только в одну сторону.
Как показали результаты проведенных триландскими экономистами исследований, управление страной будет наиболее эффективным, если три столицы будут выбраны так, что время проезда по кратчайшему пути между каждой парой столиц составит ровно d часов. Перед проведением выборов необходимо знать, сколько существует различных троек городов, удовлетворяющих описанным выше свойствам. Две тройки городов считаются различными, если в первой тройке есть хотя бы один город, которого нет во второй тройке, и наоборот.
Требуется написать программу, которая по количеству городов в Триландии и описанию дорог находит количество троек городов, которые могут быть столицами.
Пояснения к примерам
В первом примере существует единственный способ выбрать три столицы: города с номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.
Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.
Система оценивания
- Правильные решения для тестов, в которых 3 ≤ n ≤ 50, будут оцениваться из 20 баллов.
- Правильные решения для тестов, в которых 3 ≤ n ≤ 500, будут оцениваться из 40 баллов.
- Правильные решения для тестов, в которых 3 ≤ n ≤ 5000, будут оцениваться из 60 баллов.
Формат входного файла
Первая строка входного файла содержит два разделенных пробелом целых числа: количество городов в Триландии n и требуемое время в пути между столицами d. Каждая из последующих (n − 1) строк содержит описание одной дороги: пару разделенных пробелом различных целых чисел ai и bi — номера городов, которые соединены двусторонней дорогой. Каждая пара городов соединена не более чем одной дорогой.Формат выходного файла
Выходной файл должен содержать одно целое число — количество подходящих троек городов, которые могут быть выбраны столицами. В случае, если подходящих троек городов не окажется, выходной файл должен содержать ноль.Ограничения
3 ≤ n ≤ 105, 1 ≤ d < n
1 ≤ ai ≤ n, 1 ≤ bi ≤ n, ai ≠ bi
Примеры тестов
| № | Входной файл (capitals.in) |
Выходной файл (capitals.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|