| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 71 | 24 | 22 | 37.288% |
Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из $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$. Если существует несколько способов выполнить все условия маркетологов, потратив минимальное возможное количество рублей, вы можете вывести любой из них.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 24 | $\sum n \le 500,ドル $r_i \le 1000$ для всех $i$ |
| 2 | 22 | $\sum n \le 5000,ドル $r_i \le s_i$ для всех $i$ |
| 3 | 18 | $\sum n \le 100,000円,ドル $l_i \le 100 \cdot s_i,ドル $r_i = 10^9$ для всех $i$ |
| 4 | 21 | $\sum n \le 5000$ |
| 5 | 15 | $\sum n \le 100,000円$ |
2 3 1 1 3 1 2 5 7 1 2 2 4 2 1 5 5 0 1 2 2
8 0 2 3 -1
Иллюстрация для первого набора входных данных из примера:
Суммарное потраченное количество рублей равно $c_1 \cdot b_1 + c_2 \cdot b_2 + c_3 \cdot b_3 =わ 0 +たす 2 +たす 6 =わ 8$.