April 17 Graphs contest
Покраска дерева
Вам задано дерево (неориентированный связный ацикличный граф), состоящее из n вершин. Вы играете в игру на этом дереве.
Изначально все вершины белые. На первом ходу игры Вы выбираете одну вершину и красите ее в черный. Затем на каждом ходу Вы выбираете белую вершину, смежную (соединенную ребром) с любой черной вершиной и красите ее в черный.
Каждый раз, когда вы выбираете вершину (даже во время первого хода), Вы получаете количество очков, равное размеру компоненты связности, состоящей только из белых вершин, содержащей выбранную вершину. Игра заканчивается, когда все вершины покрашены в черный цвет.
Рассмотрим следующий пример:
Вершины 1 и 4 уже покрашены в черный цвет. Если выберете вершину 2, то получите 4 очка за компоненту связности, состоящую из вершин 2, 3, 5 и 6. Если выберете вершину 9, то получите 3 очка за компоненту связности, состоящую из вершин 7, 8 и 9.
Ваша задача - максимизировать количество очков, которое Вы получите.
Входные данные
Первая строка содержит одно целое число n (2 ≤ n ≤ 2 * 10^5) - количество вершин в дереве.
Каждая из следующих n − 1 строк описывает ребро дерева. Ребро i описывается двумя целыми числами u[i] и v[i] (1 ≤ u[i], v[i] ≤ n, u[i] ≠ v[i]), номерами вершин, которые оно соединяет.
Гарантируется, что заданные ребра образуют дерево.
Выходные данные
Выведите одно целое число — максимальное количество очков, которое вы получите, если будете играть оптимально.
Пример
9 1 2 2 3 2 5 2 6 1 4 4 9 9 7 9 8
36
5 1 2 1 3 2 4 2 5
14