F. Тенцинг и дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Тенцинга есть неориентированное дерево из $$$n$$$ вершин.

Определим ценность дерева с черными и белыми вершинами следующим образом: значение ребра — это абсолютная разница между количеством черных вершин в двух компонентах дерева после удаления ребра. Ценность дерева — это сумма значений по всем ребрам.

Для всех $$$k$$$ таких, что $$$0 \leq k \leq n$$$, Тенцинг хочет знать максимальную ценность дерева, когда $$$k$$$ вершин окрашены в черный цвет, а $$$n-k$$$ вершин — в белый.

Входные данные

Первая строка ввода содержит одно целое число $$$n$$$ ($$$1\leq n\leq 5000$$$) — количество вершин.

Следующие $$$n-1$$$ строк ввода содержат $$$2$$$ целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$), обозначающих ребро между вершинами $$$u_i$$$ и $$$v_i$$$. Гарантируется, что заданные ребра образуют дерево.

Выходные данные

Выведите $$$n+1$$$ число. Число $$$i$$$ является ответом на вопрос $$$k=i-1$$$.

Примеры
Входные данные
4
1 2
3 2
2 4
Выходные данные
0 3 4 5 6
Входные данные
1
Выходные данные
0 0
Примечание

Рассмотрим первый пример. Когда $$$k=2$$$, Тенцинг может покрасить вершины $$$1$$$ и $$$2$$$ в черный цвет, тогда значение ребра $$$(1,2)$$$ равно 0, а значения остальных ребер все равны $$$2$$$. Таким образом, ценность этого дерева равна $$$4$$$.