Задача D. Маршруты Красной поляны Имя входного фай...

Задача D. Маршруты Красной поляны
Имя входного файла: stdin
Имя выходного файла: stdout
Ограничение по времени: 0.5 second
Ограничение по памяти: 512 megabytes
На известном курорте Красная поляна для туристов есть N привлекательных для отдыха мест,
между которыми проложено N дорожек одинаковой длины. По каждой дорожке можно переме-
щаться в любую сторону. Дорожки устроены так, что из любого места можно добраться в любое
другое, однако иногда для этого приходится делать слишком много перемещений. Прежде чем про-
кладыватьновыедорожки,Администрациякурортахочетвыяснить,сколькосуществуетразличных
путей между всеми парами мест для отдыха, расположенными друг от друга дальше всего.
Под «местами, расположенными друг от друга дальше всего,» следует понимать пары, кратчай-
шее расстояние между которыми максимально. В качестве ответа требуется посчитать суммарное
количество кратчайших путей между всеми подобными парами мест.
Формат входных данных
В первой строке находится число N (3 ⩽ N ⩽ 200 000). В каждой из следующих N строк
находятся 2 числа — номера мест отдыха, между которыми проложена соответствующая дорожка.
Гарантируется, что все дорожки соединяют разные пары мест отдыха.
Формат выходных данных
Выведите одно число — количество кратчайших путей между между всеми парами наиболее
удаленных друг от друга мест для отдыха.
Примеры
stdin stdout
6
1 2
1 3
2 4
4 3
4 5
4 6
4
1 2
1 3
1 4 Реши на c++