Пошук скарбів

Обмеження: 2 сек., 256 МіБ

Цього року фінал ICPC проходив на острові Пхукет, а на островах часто бувають закопані скарби, ще й Дракон поблизу, а дракони переважно охороняють скарби. Все сходилось, тож команда, не витрачаючи сил на інші заняття (розв’язування задачок), вирішила знайти скарб.

Проаналізувавши карту острова було виявлено \(n\) галявин, пронумерованих від 1 до \(n\), на яких може бути закопаний скарб. Учасники якраз зараз стоять біля першої з них. Всього на острові є \(n-1\) дорога, яка з’єднує ці галявини. Також існує шлях між кожною парою галявин, тобто цей граф є деревом.

Скарб розташований на рівно одній галявині з однаковою імовірністю. Тобто імовірність того, що скарб знаходиться на \(і\)-ій галявині рівна \(\frac{1}{n}\). Кожну дорогу команда долає за 1 годину, перевірити чи є скарб на даній галявині вони вміють миттєво.

Команда обирає такий маршрут, щоб мінімізувати математичне очікування часу, коли вони знайдуть скарб. Зауважте, що коли вони обійшли \(n-1\) різних галявин та не знайшли скарбу, їм теж потрібно дістатись останньої, щоб забрати скарб.

Вам ж потрібно знайти це мінімальне математичне сподівання.

Вхідні дані

У першому рядку задано одне натуральне число \(n\) — кількість галявин.

У наступних \(n - 1\) рядках задано по 2 натуральних числа \(a_i\) та \(b_i\), що означає, що галявина з номером \(a_i\) з’єднана з галявиною з номером \(b_i\).

Спочатку команда знаходиться на галявині з номером 1.

Вихідні дані

Нехай \(m\) — мінімальне математичне сподівання часу, коли здайдуть скарб.

У єдиному рядку виведіть число \(m \cdot n\). Гарантується, що це число буде цілим.

Обмеження

\(1 \le n \le 10^5\),

\(1 \le a_i, b_i \le n\),

\(a_i \ne b_i\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 2 1 3 3 4 3 5	14

Примітки

Оптимаьний шлях: 1, 2, 1, 3, 4, 3, 5.

1. якщо скарб на 1-шій галявині, тоді їм потрібно 0 годин.

2. якщо скарб на 2-гій галявині, тоді їм потрібно 1 година.

3. якщо скарб на 3-тій галявині, тоді їм потрібно 3 години.

4. якщо скарб на 4-тій галявині, тоді їм потрібно 4 години.

5. якщо скарб на 5-тій галявині, тоді їм потрібно 6 годин.

Отже, \(m = \frac{0+1+3+4+6}{5}\), відповідь \(=n \cdot m=14\).