#1918. [GESP202512 六级] 路径覆盖

[GESP202512 六级] 路径覆盖

题目描述

给定一棵有 nn 结点的有根树 TT,结点依次以 1,2,…,n1,2,\ldots,n 编号,根结点编号为 11。方便起见,编号为 ii 的结点称为结点 ii。

初始时 TT 中的结点均为白色。你需要将 TT 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 ii 染为黑色需要代价 cic_i,你需要在满足以上条件的情况下,最小化染色代价之和。

叶子是指 TT 中没有子结点的结点。

输入格式

第一行,一个正整数 nn,表示结点数量。

第二行,n−1n-1 个正整数 f2,f3,…,fnf_2,f_3,\ldots,f_n,其中 fif_i 表示结点 ii 的父结点的编号,保证 $f_i

输出格式

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

样例

4
1 2 3
5 6 2 3
2
7
1 1 2 2 3 3
64 16 15 4 3 2 1
10

题目来源:洛谷 P14919