Задача №115138. Дерево на Манхеттене
Однажды мальчик Вова нашел корневое дерево\(^\dagger\) из \(n\) вершин, \(i\)-я вершина которого была соединена со своим предком \(p_i\) (\(p_i < i\)) ребром, с записанным на нём числом \(c_i\). Корнем является вершина \(1\). Увидев его, Вова сразу же придумал интереснейшую задачу, которую вам предстоит решить.
Выкладыванием дерева на прямую назовём сопоставление каждой вершине \(v\) целого числа \(x_v\) \((1 \le x_v \le n)\), при котором разным вершинам соответствуют разные числа, а каждое поддерево является последовательным подотрезком.
Проще говоря, выкладывание — это такая перестановка\(^{\ddagger}\) на вершинах, что для любой вершины \(v\), если отсортировать значения \(x_u\) всех вершин \(u\) в поддереве вершины \(v\), то образуется отрезок целых чисел \([l, r]\) для каких-то \(1 \le l \le r \le n\).
Стоимостью выкладывания назовём величину \(\sum_{v=2}^{n} {|x_v - x_{p_v}| \cdot c_v}\).
Посчитайте минимальную стоимость выкладывания для данного вам дерева.
\(^\dagger\) Дерево – это связный неориентированный граф без циклов. Корневое дерево — дерево с выделенной вершиной, которую называют корнем.
\(^\ddagger\) Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Первая строка содержит одно целое число \(n\) (\(2 \le n \le 5000\)) — количество вершин в дереве.
Затем следуют \(n - 1\) строк, \(i\)-я из которых содержит два целых числа \(p_{i+1}\) и \(c_{i+1}\) \((1 \le p_{i+1} \le i, 0 \le c_{i+1} \le 10^{11})\) — предок \((i+1)\)-й вершины и число, записанное на ребре из \(i+1\) в \(p_{i+1}\).
В единственной строке выведите одно число — минимальную стоимость выкладывания данного вам дерева.
Можно показать, что добиться на первом тесте из условия стоимости выкладывания меньше, чем 21 нельзя. Данная стоимость получается с помощью выкладывания \(x = \{4, 3, 5, 2, 1\}\).
Аналогично, для второго теста стоимости выкладывания меньше, чем 56 получить нельзя. Пример выкладывания с данной стоимостью \(x = \{6, 5, 7, 1, 4, 3, 8, 2\}\).
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Обозначим через \(d_i\) — количество сыновей вершины \(i\), то есть количество вершин \(v\) таких что \(p_v = i\).
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(c_i\) | \(d_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 8 | \(n \le 8\) | – | – | 0 | |
| 2 | 13 | \(n \le 50\) | – | \(d_i \le 8\) | 0 – 1 | |
| 3 | 17 | \(n \le 50\) | – | \(d_i \le 20\) | 0 – 2 | |
| 4 | 23 | \(n \le 50\) | – | – | 0 – 3 | |
| 5 | 19 | – | \(c_i = 1\) | – | – | |
| 6 | 20 | – | – | – | 0 – 5 | |
5 1 6 1 5 2 4 2 3
21
8 1 6 1 9 2 2 2 9 5 4 3 9 6 11
56