g6-07502. 染色方案·最小代价

题目描述

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。结点 $i$ 染成第 $k$ 种颜色（ $k = 1, 2, 3$ ）需要代价 $c_{i, k}$ 。要求任意一对父子结点颜色不同。

求满足要求的最小总代价。

第一行一个整数 $n$ 。

接下来 $n$ 行，第 $i$ 行三个整数 $c_{i, 1}, c_{i, 2}, c_{i, 3}$ 。

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

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

输入：

输出：

$1$ 号染颜色 $1$ （代价 $1$ ）， $2$ 号染颜色 $2$ （代价 $1$ ），父子不同，总代价 $2$ 。

输入：

输出：

链 $1 - 2 - 3$ ： $1$ 染颜色 $2$ （ $1$ ）、 $2$ 染颜色 $1$ （ $1$ ）、 $3$ 染颜色 $2$ （ $1$ ），总代价 $3$ 。