Перестановки деревьев
Перестановки деревьев
Однажды мистер Кул создал дерево (неориентированный связный граф без циклов) из n вершин, присвоив каждой вершине i > 1 два числа: pi
< i - прямой предок вершины i и wi
- вес ребра между вершиной i и pi
. Вершина 1 является корнем, поэтому у нее нет предков.
Вы хотели узнать, какое дерево построил мистер Кул, но мистер Кул отказался это сказать, хотя и дал вам наводку:
Он написал следующие числа в одной строке. Так он получил массив b длины 2 * n - 2.
b = [p2
, w2
, p3
, w3
, ..., pn-1
, wn-1
, pn
, wn
]
Затем он случайно перемешал его. Так он получил массив a, и мистер Кул подарил его Вам. Поскольку восстановить дерево, зная только значения массива a, невозможно, Вам пришлось решить другую задачу.
Назовем дерево k-длинным, если на пути между вершинами 1 и n расположено ровно k ребер.
Назовем дерево k-совершенным, если оно k-длинно и сумма весов ребер на пути между вершиной 1 и вершиной n максимальна среди всех возможных k-длинных деревьев, которые мог построить мистер Кул.
Вам следует вывести сумму весов ребер на пути между вершиной 1 и вершиной n для всех возможных k-совершенных деревьев. Выведите -1, если г-н Кул не может построить некое k-длинное дерево.
Входные данные
Первая строка содержит одно целое число n (2 ≤ n ≤ 105
) - количество вершин в дереве.
Вторая строка содержит 2 * n - 2 целых чисел a1
, a2
, ..., a2n-2
(1 ≤ ai
≤ n - 1) - элементы массива a.
Выходные данные
В одной строке выведите n - 1 целых чисел w1
, w2
, w3
, ..., wn-1
, где wk
— сумма весов ребер на пути между вершиной 1 и вершиной n в k-совершенном дереве. Если i-длинного дерева нет, то wi
должно быть равно -1.
Пояснение
В первом примере 1-совершенное дерево определяется массивом [1, 2, 1, 2] (т. е. p2
= 1, w2
= 2, p3
= 1, w3
= 2).
2-совершенное дерево определяется массивом [1, 2, 2, 1] (т. е. p2
= 1, w2
= 2, p3
= 2, w3
= 1). Ниже приведены иллюстрации 1-совершенного дерева и 2-совершенного дерева соответственно (путь от вершины 1 до вершины n нарисован жирными линиями):
Во втором примере нет k-совершенных деревьев, которые можно получить перестановкой массива a.
В третьем примере можно получить только 4-совершенное дерево и 5-совершенное дерево. Они определяются массивами [1, 4, 2, 4, 3, 4, 4, 4, 4, 5] и [1, 4, 2, 4, 3, 4, 4, 4, 5, 4] соответственно. Вот иллюстрации к ним:
3 1 1 2 2
2 3
3 2 2 2 2
-1 -1
6 1 4 5 4 4 4 3 4 4 2
-1 -1 -1 17 20