g6-07498. 哨塔部署·最小代价

题目描述

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。在结点 $i$ 上修建哨塔需要代价 $c_{i}$ 。

要求：每一条树边的两个端点中，至少有一个端点修建了哨塔。求满足要求的最小总代价。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $c_{1}, c_{2}, \dots, c_{n}$ 。

第三行 $n - 1$ 个整数 $f_{2}, f_{3}, \dots, f_{n}$ ，其中 $f_{i}$ 表示结点 $i$ 的父亲，保证 $f_{i} < i$ （ $n = 1$ 时该行为空）。

一行一个整数，表示最小总代价。

输入：

3
5 2 5
1 2

输出：

树是一条链 $1 - 2 - 3$ 。只在 $2$ 号建塔：边 $(1, 2)$ 与 $(2, 3)$ 都被覆盖，总代价 $2$ ，是最小的。

输入：

5
10 1 1 1 1
1 1 1 1

输出：

在 $2, 3, 4, 5$ 号建塔（各 $1$ ），四条边全部被覆盖，总代价 $4$ ；比在 $1$ 号建塔（代价 $10$ ）便宜。