路径覆盖

题目描述

给定⼀棵有 个结点的有根树 ，结点依次以 编号，根结点编号为 。⽅便起见，编号为 的结点称为结 点 。 初始时 中的结点均为⽩⾊。你需要将 中的若⼲个结点染为⿊⾊，使得所有叶⼦到根的路径上⾄少有⼀个⿊⾊结 点。将结点 染为⿊⾊需要代价 ，你需要在满⾜以上条件的情况下，最⼩化染⾊代价之和。 叶⼦是指 中没有⼦结点的结点。

输入格式

第⼀⾏，⼀个正整数 ，表⽰结点数量。 第⼆⾏， 个正整数 ，其中 表⽰结点 的⽗结点的编号，保证 。 第三⾏， 个正整数 ，其中 表⽰将结点 染为⿊⾊所需的代价。

输出格式

⼀⾏，⼀个整数，表⽰在满⾜所有叶⼦到根的路径上⾄少有⼀个⿊⾊结点的前提下，染⾊代价之和的最⼩值。

样例输入 #1

4
1 2 3
5 6 2 3

样例输出 #1

2

样例输入 #2

7
1 1 2 2 3 3
64 16 15 4 3 2 1

样例输出 #2

10

数据范围

对于 40% 的测试点，保证 。 对于另外 20% 的测试点，保证 。 对于所有测试点，保证 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。