Олимпиадный тренинг

Задача . D. Расстановка весов ребер корневого дерева

Задача

Вам задано корневое дерево из $n$ вершин. Вершины пронумерованы от $1$ до $n$. Корнем может быть любая из вершин.

Дерево — это связный неориентированный граф без циклов. Корневое дерево — дерево с выделенной вершиной, которую называют корнем.

Дерево задано массивом предков $b$, содержащим $n$ чисeл: $b_i$ — предок вершины с номером $i$. Предком вершины $u$ называется такая вершина, которая является следующей вершиной на простом пути от $u$ к корню. Например, на простом пути из $5$ в $3$ (корень), следующая вершина будет $1$, таким образом, предком вершины $5$ является вершина $1$.

У корня предка нет, для него в качестве $b_i$ используется значение $i$ (таким образом, корень — единственная вершина, для которой $b_i=i$).

Например, если $n=5$ и $b=[3, 1, 3, 3, 1]$, то дерево выглядит следующим образом.

$\text{[math]}$ Пример корневого дерева для $n=5$, корень дерева — вершина $3$.

Задан массив $p$ — перестановка вершин дерева. Если это возможно, расставьте целочисленные положительные веса на всех ребрах данного дерева так, чтобы вершины, отсортированные по увеличению расстояния от корня, образовывали заданную перестановку $p$.

Иными словами, по заданной перестановке вершин $p$ необходимо подобрать такие положительные веса рёбер, чтобы выполнялось неравенство $dist[p_i]<dist[p_{i+1}]$ для всех $i$ от $1$ до $n-1$, где $dist[u]$ — сумма весов рёбер на пути от корня до $u$. В частности, $dist[u]=0$, если вершина $u$ является корнем дерева.

Например, пусть $p=[3, 1, 2, 5, 4]$. В этом случае следующие веса ребер удовлетворяют этой перестановке:

ребро ($3, 4$) имеет вес $102$;
ребро ($3, 1$) имеет вес $1$;
ребро ($1, 2$) имеет вес $10$;
ребро ($1, 5$) имеет вес $100$.

В этом случае массив расстояний от корня имеет вид: $dist=[1,11,0,102,101]$. Если вершины отсортировать по возрастанию расстояний, то получится заданная перестановка $p$.

Выведите искомые веса рёбер или определите, что подходящего способа назначить веса не существует. Если решений несколько, то выведите любое из них.

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

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

Каждый набор входных данных состоит из трех строк.

В первой из них записано целое число $n$ ($1 \le n \le 2 \cdot 10^5$) — количество вершин в дереве.

Во второй записано $n$ целых чисел $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$). Гарантируется, что массив $b$ кодирует некоторое корневое дерево.

В третьей строке задана перестановка $p$: $n$ различных целых чисел $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$).

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

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

Для каждого набора входных данных выведите ответ на отдельной строке.

Если решение существует, то выведите массив из $n$ целых чисел $w_1, w_2, \dots, w_n$, где $w_i$ — вес ребра, которое ведёт из $b_i$ в $i$. Для корня такого ребра не существует, поэтому используйте значение $w_i=0$. Для всех остальных вершин значения $w_i$ должны удовлетворять неравенству $1 \le w_i \le 10^9$. Среди значений $w_i$ могут быть равные числа, но все суммы весов ребер от корня до вершин должны быть различны и удовлетворять заданной перестановке.

Если решений несколько, выведите любое из них.

Если решения не существует, то выведите -1.

Примечание

Первый набор входных данных примера разобран в основной части условия.

Во втором наборе входных данных примера невозможно расставить целочисленные положительные веса так, чтобы получить заданную перестановку вершин.

Примеры

№	Входные данные	Выходные данные
1	4 5 3 1 3 3 1 3 1 2 5 4 3 1 1 2 3 1 2 7 1 1 2 3 4 5 6 1 2 3 4 5 6 7 6 4 4 4 4 1 1 4 2 1 5 6 3	1 10 0 102 100 -1 0 3 100 1 1 2 4 6 5 10 0 2 3

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет