| Автор: | Иван Кобец | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Дано дерево, состоящее из n вершин. Корнем дерева считается вершина под номером 1. Необходимо удалить одно ребро из дерева (образовав тем самым еще одно дерево с новым корнем) так, чтобы сумма расстояний от корня до всех вершин была минимально возможной. Напишите программу, которая определит эту сумму.
В первой строке записано целое число n - количество вершин в дереве.
В следующих n − 1 строках записано по два различных целых числа ai и bi - вершины дерева, которые соединены между собой.
Выведите одно целое число - минимально возможную сумму расстояний от корня до всех вершин.
2 ≤ n ≤ 105
1 ≤ ai, bi ≤ n
Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| n | ||||
| 1 | 15 | 2 ≤ n ≤ 100 | полная | |
| 2 | 25 | 2 ≤ n ≤ 1000 | 1 | полная |
| 3 | 60 | 2 ≤ n ≤ 105 | 1, 2 | полная |
Минимальную сумму расстояний от корня до всех вершин можно получить, удалив ребро между вершинами 4 и 9. Тогда сумма расстояний от корня до всех вершин первого дерева будет 14, а второго (с корнем в вершине 9) 1.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|