27175번 - Оптимизация закупок 서브태스크스페셜 저지다국어

Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из $n$ вершин, пронумерованных от $1$ до $n$ с корнем в вершине номер $1$. В каждой вершине имеется пункт проката. Пункт, расположенный в $i$-й вершине, закупает оборудование по цене $c_i$ рублей за комплект.

Пусть $a_i$ --- суммарное количество комплектов горнолыжного оборудования, которое будет закуплено во всех пунктах проката, находящихся в поддереве вершины номер $i$. Согласно маркетинговым исследованиям для каждого $i$ эта величина должна находиться в диапазоне: $l_i \le a_i \le r_i$.

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

Напомним, что граф называется деревом, если он связный и не содержит циклов. Между любыми двумя вершинами в дереве существует ровно один простой путь. Корневым деревом называется дерево, в котором есть одна выделенная вершина --- корень. Поддеревом вершины $v$ называют множество всех вершин, для которых вершина $v$ лежит на пути от соответствующей вершины до корня. Обратите внимание, что сама вершина $v$ тоже входит в это множество. Родителем вершины $v$ называется такая вершина $p_v$, что $v$ и $p_v$ соединены ребром, и $p_v$ лежит на пути от $v$ до корня.

Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число $t$ --- количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $n$ ($1 \le n \le 100\,000$) --- количество вершин в дереве.

Во второй строке даны $n - 1$ целых чисел $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), обозначающих, что родителем вершины $i$ является вершина $p_i$.

В следующей строке даны $n$ целых чисел $c_1, \ldots, c_n$ ($1 \le c_i \le 10^9$), где $c_i$ --- цена закупки одного комплекта оборудования пунктом проката номер $i$.

В следующих $n$ строках даны по два целых числа $l_i$ и $r_i$ ($0 \le l_i \le r_i \le 10^9$) --- ограничения на общее количество комплектов горнолыжного оборудования в пунктах проката, находящихся в поддереве вершины номер $i$, к началу сезона.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $100\,000$.

Для каждого набора входных данных выведите ответ в следующем формате.

Если невозможно выполнить все условия маркетологов, в единственной строке выведите $-1$.

Иначе, в первой строке выведите минимальное количество рублей, которое необходимо потратить на закупку горнолыжного оборудования всем пунктам сети суммарно. Во второй строке выведите $n$ целых чисел $b_i$, где $b_i$ равно количеству комплектов, которое необходимо закупить пункту проката номер $i$. Если существует несколько способов выполнить все условия маркетологов, потратив минимальное возможное количество рублей, вы можете вывести любой из них.

Иллюстрация для первого набора входных данных из примера:

Суммарное потраченное количество рублей равно $c_1 \cdot b_1 + c_2 \cdot b_2 + c_3 \cdot b_3 = 0 + 2 + 6 = 8$.