路径覆盖

1 秒 / 测试点 · 512 MiB · 18 个测试点。

题目描述

给定一棵有 $n$ 个结点的有根树 $T$ ，结点依次以 $1,2,...,n$ 编号，根结点编号为 $1$ 。方便起见，编号为 $i$ 的结点称为结

点 $i$ 。

初始时 $T$ 中的结点均为白色。你需要将 $T$ 中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结

点。将结点 $i$ 染为黑色需要代价 $c_{i}$ ，你需要在满足以上条件的情况下，最小化染色代价之和。

叶子是指 $T$ 中没有子结点的结点。

第一行，一个正整数 $n$ ，表示结点数量。

第二行， $n-1$ 个正整数 $f_{2},f_{3},...,f_{n}$ ，其中 $f_{i}$ 表示结点 $i$ 的父结点的编号，保证 $f_{i}<i$ 。

第三行， $n$ 个正整数 $c_{1},c_{2},...,c_{n}$ ，其中 $c_{i}$ 表示将结点 $i$ 染为黑色所需的代价。

一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。

1421 2 335 6 2 3

1721 1 2 2 3 3364 16 15 4 3 2 1

对于 40% 的测试点，保证 $2\le n\le 16$ 。

对于另外 20% 的测试点，保证 $f_{i}=i-1$ 。

对于所有测试点，保证 $2\le n\le 10^{5}$ ， $1\le c_{i}\le 10^{9}$ 。