Новый центр района
В районе 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-битный тип.
Комментарии