Областная олимпиада по информатике 2020 год, 9-11 классы


Задача E. Есмахан и стартап

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Есмахан - начал стартап по разведению моржов. Он нанял $n-1$ работника. Есмахан - сотрудник номер $1$, все остальные пронумерованы от $2$ до $n$. У каждого из работников есть один непосредственный начальник $p_i$. У Есмахан нет начальников. Гарантируется, что значения $p_i$ образуют дерево. Теперь Есмахан должен им заплатить. Работник с номером $i$ хочет получить $a_i$ тенге. Пусть $i$ работник получит $b_i$ тенге, тогда его недовольство будет $|a_i - b_i|$. У Есмахана есть принцип - каждый работник должен получить больше чем любой его подчиненный. Вам нужно распределить зарплаты так чтобы суммарное недовольство было минимально.
Формат входного файла
В первой строке одно целое число $n$ $(1 <= n <= 200000)$. Во второй строке $n - 1$ целых чисел $p_2, p_3, ... p_n$ $(1 <= p_i <= i - 1)$ - номера начальников работников. В третей строке $n$ целых чисел $a_1, a_2, ... a_n$ $(1 <= a_i <= 10^9)$ - ожидания работников.
Формат выходного файла
Выведите одно целое число - минимальное суммарное недовольство работников.
Система оценки
Данная задача содержит ровно $25$ тестов и каждый оценивается в $4$ баллов.
  1. Тест из условия.
  2. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$, у каждого работника не больше одного подчиненного | 2 теста.
  3. $1 <= n <= 1000$, $1 <= a_i <= 1000$ для $1 <= i <= n$ | 2 теста.
  4. $1 <= n <= 1000$, у каждого работника не больше одного подчиненного | 2 теста.
  5. $1 <= n <= 1000$ | 3 теста.
  6. $1 <= n <= 200000$, у каждого работника не больше одного подчиненного | 5 тестов.
  7. $1 <= n <= 200000$ | 10 тестов.
Пример:
Вход
7
1 2 1 1 5 6
1 2 3 1 4 3 3
Ответ
7
Замечание
Ответ в примере $b={5, 4, 3, 1, 4, 3, 2}$ ( Batyr Sardarbekov )
посмотреть в олимпиаде

Комментарий/решение:

  0
2021-09-23 12:38:26.0 #

показать/скрыть код