Задача Railway
В стране Олимпия произошел экономический кризис. Не обошел он и местную железную дорогу. После очередных реформ железная дорога состоит из N станций и N-1 перегонов, которые соединяют эти станции. Каждая станция может быть непосредственно соединена не более, чем с шестью другими станциями. Между любой парой разных станций существует только один способ добраться от первой станции до второй.
Наибольшие проблемы железной дороге Олимпии причиняют расхитители, которые ночью снимают с железнодорожных путей рельсы. Воры могут начинать свое движение с любой станции и беспрепятственно двигаться к любой другой станции по рельсам (благо поезда ночами не ходят - путь свободен). При этом никакую станцию им нельзя проезжать больше одного раза - могут засечь.
Дирекция железной дороги просит Вас определить наибольший ущерб и количество способов, которыми он может быть причинен.
Технические условия: Программа должна прочитать с клавиатуры натуральное число N (1 <= N <= 100000) – количество железнодорожных станций, а потом N-1 тройку натуральных чисел. Каждая тройка содержит информацию об одном перегоне. Первые два числа тройки – номера станций, которые соединены этим перегоном, третье число – длина перегона в километрах (длина не может превышать 1000 км).
Программа должна вывести на экран два числа через пробел – наибольший ущерб (суммарная длина путей, которые расхитители могут разобрать) и количество способов, которыми он может быть причинен.
Примеры:
Ввод: 3 1 2 1 2 3 2
Вывод: 3 2
Ввод: 5 1 2 1 1 3 1 1 4 1 1 5 1
Вывод: 2 12