Коба и бананове дерево
Коба и бананове дерево
Ваш друг Коба — умная обезьяна, и он любит есть бананы. Он вырвал с корнем банановое дерево, которое нашел сегодня утром в джунглях (Коба очень сильный), и отнес его в свое логово. У Кобы сегодня будет три закуски. Поэтому он думает как срезать две ветки дерева чтобы разделить его на три части (Коба будет есть бананы с каждой из частей за один перекус). Коба хочет, чтобы разница в количестве бананов между частью с наибольшим количеством бананов и частью с наименьшим количеством бананов была как можно меньше (Коба старается придерживаться сбалансированной диеты). Будем называть такой разрез оптимальным.
Банановое дерево, которое Коба взял в свое логово, представляет собой дерево, в вершинах которого находятся бананы, пронумерованные с 1 до n. Дерево содержит n − 1 ветвь, которые служат соединительными звеньями между этими бананами. То есть бананы являются вершинами дерева, а ветки ребрами.
У Вас имеется структура дерева, которое Коба взял в свое логово. Исходя из этого, найдите разницу в количестве бананов между частью с наибольшим количеством бананов и частью с наименьшим количеством бананов в оптимальном разрезе.
Входные данные
В первой строке записано одно целое число n (3 ≤ n ≤ 2 * 105
) - количество бананов. В каждой из следующих n - 1 строк записано по два целых числа ui
, vi
(1 ≤ ui
, vi
≤ n) - пары бананов, соединенных веткой (ребром).
Выходные данные
Выведите одно целое число - разницу в количестве бананов между частью с наибольшим числом бананов и частью с наименьшим числом бананов в оптимальном разрезе.
Пояснение
Пример 1. Если мы обрежем ветки между 2 и 3, 4 и 5, то дерево будет разделено на три части размером 2, 2 и 1. Ответ 2 − 1 = 1.
Пример 2. Оптимальные разрезы приведены на рисунке, приведенном выше. Размеры частей, получающихся в результате распилов, равны 4, 2 и 3. Ответ 4 − 2 = 2.
5 1 2 2 3 3 4 4 5
1
9 1 3 3 2 3 4 3 5 5 6 5 7 7 8 7 9
2