У Тенцинга есть неориентированное дерево из \(n\) вершин.
Определим ценность дерева с черными и белыми вершинами следующим образом: значение ребра — это абсолютная разница между количеством черных вершин в двух компонентах дерева после удаления ребра. Ценность дерева — это сумма значений по всем ребрам.
Для всех \(k\) таких, что \(0 \leq k \leq n\), Тенцинг хочет знать максимальную ценность дерева, когда \(k\) вершин окрашены в черный цвет, а \(n-k\) вершин — в белый.
Выходные данные
Выведите \(n+1\) число. Число \(i\) является ответом на вопрос \(k=i-1\).
Примечание
Рассмотрим первый пример. Когда \(k=2\), Тенцинг может покрасить вершины \(1\) и \(2\) в черный цвет, тогда значение ребра \((1,2)\) равно 0, а значения остальных ребер все равны \(2\). Таким образом, ценность этого дерева равна \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
3 2
2 4
|
0 3 4 5 6
|
|
2
|
1
|
0 0
|