Розфарбування дерева#11002

Розфарбування дерева

1 секунда

128 мегабайтів

Легка

Вам задано дерево (неорієнтований зв'язний ациклічний граф), що складається з $n$ вершин. Ви граєте у гру на цьому дереві.

Спочатку всі вершини пофарбовані у білий колір. На першому ході Ви обираєте одну вершину і перефарбовуєте її у чорний колір. Далі на кожному ході Ви обираєте білу вершину, суміжну (тобто з'єднану ребром) хоча б з однією чорною вершиною, і перефарбовуєте її у чорний колір.

Кожного разу, коли Ви обираєте вершину (включаючи перший хід), Ви отримуєте кількість очок, що дорівнює розміру компоненти зв'язності, яка складається тільки з білих вершин і містить обрану вершину. Гра закінчується, коли всі вершини стануть чорними.

Розглянемо наступний приклад:

Вершини $1$ і $4$ вже пофарбовані у чорний колір. Якщо обрати вершину $2$ , то Ви отримаєте $4$ очки за компоненту зв'язності, що складається з вершин $2, 3, 5$ і $6$ . Якщо обрати вершину $9$ , то Ви отримаєте $3$ очки за компоненту зв'язності, що складається з вершин $7, 8$ і $9$ .

Ваше завдання — максимізувати загальну кількість очок, яку Ви зможете набрати.

Вхідні дані

Перший рядок містить одне ціле число $n (2 \leq n \leq 2 \cdot 1 0^{5})$ n~(2 \le n \le 2 \cdot 10^5) — кількість вершин у дереві.

Кожен з наступних $n - 1$ n - 1 рядків описує одне ребро дерева. Ребро $i$ задається двома цілими числами $u_{i}$ u_i і $v_{i} (1 \leq u_{i}, v_{i} \leq n, u_{i} \neq = v_{i})$ v_i~(1 \le u_i, v_i \le n,\ u_i \ne v_i) — номерами вершин, які воно з'єднує.

Гарантується, що задані ребра утворюють дерево.

Вихідні дані

Виведіть одне ціле число — максимальну кількість очок, яку Ви отримаєте при оптимальній грі.

Приклади

Приклад 1

Приклад 2