Вы вероятно слышали про двенадцать подвигов Геракла, однако знаете ли вы про тринадцатый? Принято считать, что ему потребовалась дюжина лет, чтобы выполнить двенадцать подвигов, то есть в среднем год, чтобы выполнить каждый из них. Поскольку в наши дни время течет быстрее, у вас есть минуты, а не месяцы, чтобы решить эту задачу. Справитесь ли вы?
В этой задаче вам дано дерево с \(n\) вершинами, каждая из которых имеет вес. Дерево — это связный граф с \(n - 1\) ребром.
Определим \(k\)-раскраску дерева как назначение одного из \(k\) цветов каждому из его ребер. Обратите внимание, что вы не обязаны использовать все \(k\) цветов.
Подграф цвета \(x\) состоит из тех ребер исходного графа, которым был назначен цвет \(x\), и только тех вершин, которые смежны с хотя бы одним из таких ребер. Поэтому в таком подграфе нет вершин степени \(0\).
Весом компоненты связности назовем сумму весов её вершин. Весом подграфа назовем максимальный из весов компонент связности этого подграфа. Вес пустого подграфа будем считать равным \(0\).
Определим вес \(k\)-раскраски как сумму весов подграфов всех \(k\) цветов. Дано дерево, для каждого \(k\) от \(1\) до \(n - 1\) вычислите максимальный возможный вес \(k\)-раскраски.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(n - 1\) целое число, где \(i\)-е число должно равняться максимальному весу \(i\)-раскраски дерева.
Примечание
Оптимальные \(k\)-раскраски дерева из первого набора входных данных следующие:
В \(1\)-раскраске все ребра имеют одинаковый цвет. Подграф цвета \(1\) содержит все ребра и вершины исходного графа. Поэтому его вес равен \(3 + 5 + 4 + 6 = 18\).
В оптимальной \(2\)-раскраске ребрам \((2, 1)\) и \((3,1)\) назначен цвет \(1\). Ребру \((4, 3)\) — цвет \(2\). Подграф цвета \(1\) состоит из одной компоненты связности (вершины \(1, 2, 3\)) и его вес равен \(3 + 5 + 4 = 12\). Подграф цвета \(2\) состоит из двух вершин и одного ребра. Его вес равен \(4 + 6 = 10\).
В оптимальной \(3\)-раскраске всем ребрам назначены разные цвета. Поэтому подграф каждого цвета содержит одно ребро. Их веса следующие: \(3 + 4 = 7\), \(4 + 6 = 10\), \(3 + 5 = 8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
3 5 4 6
2 1
3 1
4 3
2
21 32
2 1
6
20 13 17 13 13 11
2 1
3 1
4 1
5 1
6 1
4
10 6 6 6
1 2
2 3
4 1
|
18 22 25
53
87 107 127 147 167
28 38 44
|