G. Ночной змей
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юсеф дал вам корневое дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин, где корнем является вершина $$$1$$$. Каждой вершине $$$i$$$ присвоено целое число $$$a_i$$$.

Вам нужно разбить множество всех $$$n$$$ вершин ровно на $$$k$$$ непересекающихся подмножеств $$$S_1, S_2, \dots, S_k$$$ (то есть каждая вершина должна оказаться ровно в одном из $$$k$$$ множеств) так, чтобы выполнялось следующее условие:

  • Для любого подмножества $$$S_i$$$, содержащего две или более вершин, для любой пары вершин $$$u, v \in S_i$$$ одна из них должна быть предком$$$^{\text{†}}$$$ другой (то есть все они должны лежать на одном и том же пути, идущем от корня к листу).

Оценка подмножества $$$S_i$$$ определяется как максимальное значение $$$a_u$$$ среди всех вершин $$$u$$$ в этом подмножестве. Оценка разбиения — это сумма оценок $$$k$$$ подмножеств. Иными словами, оценка разбиения равна $$$\sum\limits_{i=1}^{k} \max\limits_{u \in S_i} a_u$$$.

Для каждого целого числа $$$k$$$ от $$$1$$$ до $$$n$$$ вычислите максимальную возможную оценку разбиения. Если разбить дерево ровно на $$$k$$$ подмножеств, удовлетворяющих условию, невозможно, выведите для этого значения $$$-1$$$.

$$$^{\text{∗}}$$$Дерево — это связный граф без циклов. Корневое дерево — это дерево, в котором одна вершина выделена и называется корнем.

$$$^{\text{†}}$$$Предок вершины $$$v$$$ — это любая вершина на простом пути от $$$v$$$ к корню, включая корень, но не включая саму вершину $$$v$$$. У корня нет предков.

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

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество вершин.

Во второй строке каждого набора входных данных заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — значения вершин.

В третьей строке каждого набора входных данных заданы $$$n-1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$), где $$$p_i$$$ — родитель $$$i$$$-й вершины.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одну строку, содержащую $$$n$$$ целых чисел, разделённых пробелами. $$$k$$$-е число должно обозначать максимальную возможную оценку разбиения на $$$k$$$ подмножеств. Если разбить дерево на $$$k$$$ подмножеств невозможно, выведите для этого значения $$$-1$$$.

Пример
Входные данные
7
3
10 20 30
1 1
4
5 10 15 20
1 2 2
4
1 2 3 4
1 1 3
5
1 2 3 4 5
1 2 3 4
9
1 100 1 90 80 1 2 3 4
1 1 2 4 3 3 3 3
6
5 4 10 3 9 1
1 2 1 4 1
4
10 10 20 1
1 2 1
Выходные данные
-1 50 60
-1 35 45 50
-1 6 9 10
5 9 12 14 15
-1 -1 -1 -1 110 200 280 281 282
-1 -1 24 28 31 32
-1 30 40 41
Примечание

В первом наборе входных данных:

  • Для $$$k = 1$$$ все вершины должны находиться в одном множестве. Однако для вершин $$$2$$$ и $$$3$$$ ни одна из них не является предком другой. Поэтому корректного разбиения не существует.
  • Для $$$k = 2$$$ можно взять $$$S_1 = \{2\}$$$, $$$S_2 = \{1, 3\}$$$. Оценка этого разбиения равна $$$\max\limits_{u \in S_1} a_u + \max\limits_{u \in S_2} a_u = 20 + 30 = 50$$$. Можно показать, что это максимальная оценка.
  • Для $$$k = 3$$$ можно взять $$$S_1 = \{1\}$$$, $$$S_2 = \{2\}$$$, $$$S_3 = \{3\}$$$. Оценка этого разбиения равна $$$10 + 20 + 30 = 60$$$.
Заданное дерево в первом наборе входных данных.

Во втором наборе входных данных:

  • Для $$$k = 1$$$ все вершины должны находиться в одном множестве. Однако вершины $$$3$$$ и $$$4$$$ не лежат на одном пути от корня к листу, поэтому это невозможно.
  • Для $$$k = 2$$$ можно взять $$$S_1 = \{3\}$$$, $$$S_2 = \{1,2,4\}$$$. Оценка этого разбиения равна $$$\max\limits_{u \in S_1} a_u + \max\limits_{u \in S_2} a_u = 15 + 20 = 35$$$. Можно показать, что это максимальная оценка.
  • Для $$$k = 3$$$ можно взять $$$S_1 = \{3\}$$$, $$$S_2 = \{4\}$$$, $$$S_3 = \{1,2\}$$$. Оценка этого разбиения равна $$$15 + 20 + 10 = 45$$$. Можно показать, что это максимальная оценка.
  • Для $$$k = 4$$$ можно взять $$$S_1 = \{1\}$$$, $$$S_2 = \{2\}$$$, $$$S_3 = \{3\}$$$, $$$S_4 = \{4\}$$$. Оценка этого разбиения равна $$$5 + 10 + 15 + 20 = 50$$$.
Заданное дерево во втором наборе входных данных.