Новый центр района


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В районе n сёл, соединённых n − 1 дорогами так, что из любого села можно доехать в любое (дорожная сеть — дерево). Дорога i между сёлами u и v имеет длину w.

Акимат выбирает новый районный центр. Чтобы никому не было слишком далеко, центр выбирают в селе c, для которого наименьшая сумма квадратов расстояний от всех сёл до c:

S(c) = Σ dist(v, c)² по всем сёлам v.

Рисунок

Найдите село c с наименьшим S(c) (если таких несколько — с наименьшим номером) и само значение S(c).

Входные данные

В первой строке — число n (1 ≤ n ≤ 2 · 10⁵). В каждой из следующих n − 1 строк — три целых числа u v w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁶).

Выходные данные

Выведите номер села и значение S(c).

Пример 1

Вход:

4
1 2 1
2 3 2
3 4 3

Выход:

3 22

Пояснение

Для села 2: расстояния до сёл 1, 3, 4 равны 1, 2, 5, сумма квадратов 1 + 4 + 25 = 30. Для села 3: 9 + 4 + 9 = 22 — это меньше, и меньше не бывает.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 200.

Примечание

Значение S(c) может не поместиться в 64-битный тип.


Комментарии

Еще нет ни одного комментария.