Задача C3. Оптимальное удаление

Автор:Иван Кобец   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Дано дерево, состоящее из n вершин. Корнем дерева считается вершина под номером 1. Необходимо удалить одно ребро из дерева (образовав тем самым еще одно дерево с новым корнем) так, чтобы сумма расстояний от корня до всех вершин была минимально возможной. Напишите программу, которая определит эту сумму.

Формат входных данных

В первой строке записано целое число n - количество вершин в дереве.

В следующих n − 1 строках записано по два различных целых числа ai и bi - вершины дерева, которые соединены между собой.

Формат выходных данных

Выведите одно целое число - минимально возможную сумму расстояний от корня до всех вершин.

Ограничения

2 ≤ n ≤ 105

1 ≤ ai, bi ≤ n

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
n
1152 ≤ n ≤ 100полная
2252 ≤ n ≤ 10001полная
3602 ≤ n ≤ 1051, 2полная

Пояснение к примеру

Минимальную сумму расстояний от корня до всех вершин можно получить, удалив ребро между вершинами 4 и 9. Тогда сумма расстояний от корня до всех вершин первого дерева будет 14, а второго (с корнем в вершине 9) 1.

Примеры тестов

Стандартный вход Стандартный выход
1
10
1 2
1 3
2 4
2 5
3 6
4 9
6 7
6 8
9 10
15

0.112s 0.011s 13