Коба і бананове дерево#11293
Ваш друг Коба — розумна мавпа, і він обожнює банани. Сьогодні вранці в джунглях він вирвав з коренем бананове дерево (Коба дуже сильний) і відніс його до свого лігва. Коба планує сьогодні три перекуси, тому він думає, як зрізати дві гілки дерева, щоб розділити його на три частини (Коба буде їсти банани з кожної частини за один перекус). Коба хоче, щоб різниця в кількості бананів між частиною з найбільшою кількістю бананів і частиною з найменшою кількістю бананів була якомога меншою (Коба намагається дотримуватися збалансованої дієти). Такий розріз ми будемо називати оптимальним.
Бананове дерево, яке Коба приніс до свого лігва, є деревом, у вершинах якого знаходяться банани, пронумеровані від до . Дерево містить n - 1 гілку, які служать з'єднувальними ланками між цими бананами. Тобто банани є вершинами дерева, а гілки — ребрами.
Вам надано структуру дерева, яке Коба приніс до свого лігва. Виходячи з цього, знайдіть різницю в кількості бананів між частиною з найбільшою кількістю бананів і частиною з найменшою кількістю бананів в оптимальному розрізі.
У першому рядку записано одне ціле число (3 \leq n \leq 2 \cdot 10^5) — кількість бананів. У кожному з наступних n - 1 рядків записано по два цілих числа u_i, v_i (1 \leq u_i, v_i \leq n) — пари бананів, з'єднаних гілкою (ребром).
Виведіть одне ціле число — різницю в кількості бананів між частиною з найбільшою кількістю бананів і частиною з найменшою кількістю бананів в оптимальному розрізі.
Приклад 1
Приклад 2
Приклад 1. Якщо ми обріжемо гілки між і , і , то дерево буде розділено на три частини розміром , і . Відповідь 2 - 1 = 1.
Приклад 2. Оптимальні розрізи наведені на малюнку вище. Розміри частин, що утворюються в результаті розрізів, дорівнюють , і . Відповідь 4 - 2 = 2.