Задача №112598. Два пути
Как вы знаете, Васин брат живет во Флатландии. Во Флатландии n городов, соединенных n - 1 двухсторонней дорогой. Города пронумерованы от 1 до n . Из любого города можно добраться до любого другого.
Компания «Два пути», в которой работает Васин брат, выиграла тендер на ремонт двух путей во Флатландии. Путем называется последовательность различных городов, последовательно соединенных дорогами. Пути, которые надо отремонтировать, компания может выбрать самостоятельно. Единственное условие, накладываемое тендером, они не должны пересекаться (то есть иметь общих городов).
Известно, что прибыль, которую получит компания «Два пути», равна произведению длин выбранных двух путей. Считая длину каждой дороги один, а длину пути равной количеству дорог в ней, найдите максимальную возможную прибыль.
В первой строке записано целое число n (2 ≤ n ≤ 100 000) , где n количество городов в стране. Далее в n - 1 строке записаны сами дороги. Каждая строка содержит пару номеров соединяемых дорогами a i , b i (1 ≤ a i , b i ≤ n )
Выведите максимально возможную прибыль.
4 1 2 2 3 3 4
1
7 1 2 1 3 1 4 1 5 1 6 1 7
0
6 1 2 2 3 2 4 5 4 6 4
4