NetOI-2011 Stage 3
Railway
В стране Олимпия произошёл экономический кризис. Не обошёл он и местную железную дорогу. После очередных реформ железная дорога Олимпии состоит из N станций и N-1 перегонов, которые соединяют эти станции. Каждая станция может быть непосредственно соединена не более, чем с шестью другими станциями. Между любой парой разных станций существует только один способ добраться от первой станции ко второй.
Наибольшие проблемы железнаой дороге Олимпии причиняют расхитители, которые ночью снимают с железнодорожных путей рельсы. Воры могут начинать своё движение с любой станции и безпрепятсвенно двигаться к любой другой станции. При этом никакую станцию им нельзя проезжать более одного раза - могут засечь.
Дирекция железной дороги просит Вас определить наибольший ущерб и количество способов. которыми он может быть причинён.
Giriş verilənləri
Программа читает целое число N (1 ≤ N ≤ 100000) - количество железнодорожных станций, а далее N-1 тройку целых чисел. Каждая тройка содержит информацию об одном перегоне. Первые два числа - номеры станций, которые соединяет заданный перегон, третье число - длина перегона в километрах (длина не может превышать 1000 км).
Çıxış verilənləri
Программа должна выводить два числа через пробел - наибольший возможный ущерб (суммарная длина путей, которые расхитители могут разобрать) и количество способов, которыми он может быть причинён.
Nümunə
3 1 2 1 2 3 2
3 2