Залізниця#2775
В країні Олімпія трапилася економічна криза. Після останніх реформ залізниця Олімпії складається з станцій та N-1 перегонів, які з'єднують ці станції. Кожна станція може бути безпосередньо з'єднана не більше ніж з шістьма іншими станціями. Між будь-якою парою різних станцій існує рівно один спосіб дістатися від першої станції до другої.
Головна проблема залізниці Олімпії — це злодії, які вночі знімають рейки. Злодії можуть почати рух з будь-якої станції та прямувати до будь-якої іншої, але не можуть проходити через одну й ту ж станцію більше одного разу.
Дирекція залізниці просить вас визначити найбільший можливий збиток (сумарну довжину колій, які можуть розібрати злодії) та кількість способів його спричинити.
Програма читає ціле число (1 \leq N \leq 100{,}000) — кількість залізничних станцій, а потім N-1 трійок цілих чисел. Кожна трійка містить інформацію про один перегін: перші два числа — номери станцій, які з'єднані перегоном, третє число — довжина перегону в кілометрах (довжина не перевищує км).
Програма повинна вивести два числа через пропуск: найбільший можливий збиток (сумарну довжину колій, які можуть розібрати злодії), та кількість способів його спричинити.
Приклад 1