Задача №113909. ООШП
Открытое Объединение Шиномонтажников-Перфекционистов (ООШП) — организация, объединяющая n шиномонтажников города N. Все шиномонтажники этой организации пронумерованы последовательными целыми числами от 1 до n в порядке вступления в ООШП и объединены в одну древовидную иерархию таким образом, что шиномонтажник номер 1 является руководителем организации, а у любого другого шиномонтажника i есть непосредственный начальник p i , обязательно имеющий меньший номер. Будем говорить, что шиномонтажник v является начальником шиномонтажника u , если v встречается в цепочке непосредственных начальников от u до 1 , то есть в последовательности p u , p p u и так далее. Шиномонтажник u в таком случае называется подчинённым шиномонтажника v .
Поскольку все члены ООШП являются ещё и перфекционистами, то в ходе работы у них часто возникают споры. Будем считать, что споры могут возникать только в паре шиномонтажников, ни один из которых не является подчинённым другого. Для разрешения спора они идут к своему ближайшему общему начальнику , то есть шиномонтажнику с максимальным номером, который является начальником для каждого из спорящих. Каждый шиномонтажник кроме первого обладает некоторым уровнем перфекционизма , выражающимся целым числом c i . Накалом спора называется сумма уровней перфекционизма двух участвующих в нём шиномонтажников. Наконец, конфликтностью рабочего дня называется сумма накалов всех споров, возникших в течение этого дня.
По окончании рабочего дня шиномонтажник v считает себя эффективным руководителем , если в течение дня он помог разрешить хотя бы один спор каждому своему подчиненному. Формально говоря, это значит, что для каждого шиномонтажника u , который является подчиненным v , существует такой шиномонтажник w , что u и w конфликтовали в течение дня, а v оказался ближайшим общим начальником u и w . В частности, любой шиномонтажник, у которого нет подчинённых, автоматически считает себя эффективным руководителем.
Вы работаете программистом в ООШП и знакомы со всеми шиномонтажниками в организации. Уходя сегодня с работы, каждый шиномонтажник в компании по секрету сообщил вам, что по итогам сегодняшнего дня считает себя эффективным руководителем. Вы знаете иерархию шиномонтажников ООШП, но не знаете, какие именно споры возникали в течение дня. Теперь вам интересно, какое минимальное значение могла принять конфликтность сегодняшнего дня при условии, что каждый шиномонтажник действительно сегодня был эффективным руководителем.
В первой строке находится число n ( 3 ≤ n ≤ 200 000 ) — количество шиномонтажников в ООШП. Во второй строке находятся n - 1 целых чисел p 2 , p 3 , ..., p n ( 1 ≤ p i < i ), где p i соответствует номеру шиномонтажника, являющегося начальником шиномонтажника номер i . В третьей строке находятся n - 1 целых чисел c 2 , c 3 , ..., c n ( 1 ≤ c i ≤ 10 6 ), где c i — уровень перфекционизма i -го шиномонтажника.
Гарантируется, что при заданной структуре иерархии могла случиться такая ситуация, что к концу рабочего дня каждый шиномонтажник будет считать себя эффективным руководителем.
Выведите минимальное возможное значение конфликтности сегодняшнего дня.
Рассмотрим первый тест из условия. Чтобы достичь указанной величины конфликтности дня, необходимо, чтобы в течение дня возникли споры в парах шиномонтажников (2, 5) , (3, 4) , (3, 5) и (4, 5) .
- Шиномонтажники 3 , 4 и 5 автоматически считают себя эффективными руководителями, так как у них нет подчинённых.
- Шиномонтажник 2 считает себя эффективным руководителем, так как он помог шиномонтажнику 3 в споре с шиномонтажником 4 , а шиномонтажнику 4 в споре с шиномонтажником 3 .
- Шиномонтажник 1 считает себя эффективным руководителем, так как он помог шиномонтажникам 2 , 3 и 4 уладить их конфликты с шиномонтажником 5 , а шиномонтажнику 5 он помог уладить целых три конфликта.
Во втором примере (который подходит под ограничения второй и четвёртой, но не первой и третьей групп) оптимальное решение можно получить спорами в парах (2, 4) , (2, 5) , (3, 6) и (5, 6) . Значение конфликтности дня при таком сценарии составит (1 + 3) + (1 + 4) + (2 + 5) + (4 + 5) = 25 . Указанный набор пар не является единственным способом получить минимальное значение конфликтности.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
5 1 2 2 1 1 1 1 1
8
6 1 1 1 4 4 1 2 3 4 5
25