Codeforces Round 530 (Div. 1) |
---|
Закончено |
У Мити есть корневое дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, причем корень дерева имеет номер $$$1$$$. В каждой его вершине $$$v$$$ было записано целое число $$$a_v \ge 0$$$. Для каждой вершины $$$v$$$ Митя вычислил величину $$$s_v$$$: сумму чисел, записанных на пути от вершины $$$v$$$ до корня, а также $$$h_v$$$ — глубину вершины $$$v$$$, то есть количество вершин на пути от вершины $$$v$$$ до корня (таким образом, $$$s_1=a_1$$$, $$$h_1=1$$$).
После этого Митя уничтожил исходные значения $$$a_v$$$. К сожалению, он также случайно уничтожил все значения $$$s_v$$$ для вершин, находящихся на четной глубине (то есть тех, для которых $$$h_v$$$ является четным). Ваша задача состоит в том, чтобы восстановить значения $$$a_v$$$ для каждой из вершин либо определить, что это невозможно. Среди возможных вариантов нужно выбрать тот, при котором сумма значений $$$a_v$$$ во всем дереве является минимально возможной.
В первой строке содержится число $$$n$$$ — число вершин в дереве ($$$2 \le n \le 10^5$$$). В следующей строке заданы числа $$$p_2$$$, $$$p_3$$$, ... $$$p_n$$$, где $$$p_i$$$ обозначает номер вершины, которая является предком вершины $$$i$$$ в дереве ($$$1 \le p_i < i$$$). В последней строке входных данных содержатся целые числа $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$ ($$$-1 \le s_v \le 10^9$$$), где уничтоженные значения заменены на $$$-1$$$.
Выведите единственное число — минимально возможную сумму чисел $$$a_v$$$ в вершинах исходного дерева или $$$-1$$$, если такого дерева не существует.
5 1 1 1 1 1 -1 -1 -1 -1
1
5 1 2 3 1 1 -1 2 -1 -1
2
3 1 2 2 -1 1
-1
Название |
---|