Однажды мистер Кул создал дерево (неориентированный связный граф без циклов) из n вершин, присвоив каждой вершине i > 1 два числа: p[i]
< i - прямой предок вершины i и w[i]
- вес ребра между вершиной i и p[i]
. Вершина 1 является корнем, поэтому у нее нет предков.
Вы хотели узнать, какое дерево построил мистер Кул, но мистер Кул отказался это сказать, хотя и дал вам наводку:
Он написал следующие числа в одной строке. Так он получил массив b длины 2 * n - 2.
b = [p[2]
, w[2]
, p[3]
, w[3]
, ..., p[n-1]
, w[n-1]
, p[n]
, w[n]
]
Затем он случайно перемешал его. Так он получил массив a, и мистер Кул подарил его Вам. Поскольку восстановить дерево, зная только значения массива a, невозможно, Вам пришлось решить другую задачу.
Назовем дерево k-длинным, если на пути между вершинами 1 и n расположено ровно k ребер.
Назовем дерево k-совершенным, если оно k-длинно и сумма весов ребер на пути между вершиной 1 и вершиной n максимальна среди всех возможных k-длинных деревьев, которые мог построить мистер Кул.
Вам следует вывести сумму весов ребер на пути между вершиной 1 и вершиной n для всех возможных k-совершенных деревьев. Выведите -1, если г-н Кул не может построить некое k-длинное дерево.
Первая строка содержит одно целое число n (2 ≤ n ≤ 10^5
) - количество вершин в дереве.
Вторая строка содержит 2 * n - 2 целых чисел a[1]
, a[2]
, ..., a[2n-2]
(1 ≤ a[i]
≤ n - 1) - элементы массива a.
В одной строке выведите n - 1 целых чисел w[1]
, w[2]
, w[3]
, ..., w[n-1]
, где w[k]
— сумма весов ребер на пути между вершиной 1 и вершиной n в k-совершенном дереве. Если i-длинного дерева нет, то w[i]
должно быть равно -1.
В первом примере 1-совершенное дерево определяется массивом [1, 2, 1, 2] (т. е. p[2]
= 1, w[2]
= 2, p[3]
= 1, w[3]
= 2).
2-совершенное дерево определяется массивом [1, 2, 2, 1] (т. е. p[2]
= 1, w[2]
= 2, p[3]
= 2, w[3]
= 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] соответственно. Вот иллюстрации к ним: