Задача №114761. Оптимизация закупок
Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из \(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\). Если существует несколько способов выполнить все условия маркетологов, потратив минимальное возможное количество рублей, вы можете вывести любой из них.
Обозначим суммарное количество вершин во всех наборах входных данных за \(\sum n\). Обозначим количество вершин в поддереве вершины номер \(i\) за \(s_i\).
| Ограничения | |||||
| Подзадача | Баллы | \(\sum n\) | дополнительно | Необх. подзадачи | Информация о проверке |
| 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\) | – | У, 1, 2 | первая ошибка |
| 5 | 15 | \(\sum n \le 100\,000\) | – | У, 1–4 | первая ошибка |
Иллюстрация для первого набора входных данных из примера:
Суммарное потраченное количество рублей равно \(c_1 \cdot b_1 + c_2 \cdot b_2 + c_3 \cdot b_3 = 0 + 2 + 6 = 8\).
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