路径覆盖
题目描述
给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci ,你需要在满足以上条件的情况下,最小化染色代价之和。
叶子是指 T 中没有子结点的结点。
输入格式
第一行,一个正整数 n ,表示结点数量。
第二行, n−1 个正整数 f2, f3, …, fn ,其中 fi 表示结点 i 的父结点的编号,保证 fi<i
第三行, n 个正整数 c1, c2, …, cn,其中 ci 表示将结点 i 染为黑色所需的代价。
输出格式
一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于 40% 的测试点,保证 2 ≤n ≤16
对于另外 20% 的测试点,保证 fi=i-1
对于所有测试点,保证 2 ≤n ≤10^5, 1 ≤ci ≤10^9