nastya05112

21.07.2021 05:01

Информатика

Есть ответ 👍

Оптимальный рабочий ограничение по времени на тест 2 секунды Система иерархии в компании Михаила представляет собой дерево, где у каждого из n сотрудников, кроме самого Михаила, есть непосредственный начальник (и наоборот, у Михаила есть несколько прямых подчиненных, у некоторых из них есть свои подчиненные, и так далее). К сожалению, у Михаила скопилось много рутинной работы, которую могут выполнить только рядовые сотрудники (то есть те, у которых нет ни одного подчиненного), но чтобы передать задание сотруднику, Михаил должен попросить передать это задание каждого другого сотрудника на пути между ними. Про каждого сотрудника известно число ci — сколько ему надо заплатить, чтобы задание было передано дальше и было в конечном итоге выполнено Михаилу выбрать рядового сотрудника так, чтобы заплатить за передачу и выполнение суммарно как можно меньше. Входные данные В первой строке ввода задано число n — количество сотрудников в компании (1⩽n⩽10е5). В следующей строке через пробел перечислены номера начальников: на i-м месте стоит номер непосредственного начальника i-го сотрудника. Число 0 означает, что это Михаил, и у него начальника нет. В третьей строке так же перечислены ci — сколько придется заплатить i-му сотруднику за передачу или выполнения задания (0⩽ci⩽10е9). Гарантируется, что себе Михаил ничего платить не должен. Выходные данные Выведите единственное число — минимальное суммарное число денег, с которым Михаилу придется расстаться. Пример входные данные
7
0 1 1 2 2 3 3
0 10 11 5 6 1 2
выходные данные
12
Можете написать идею алгоритма или код (желательно на плюсах)