SP3912 MTREECOL - Color a tree
题目描述
Bob对一棵树的数据结构非常感兴趣。树是一个有向图,其中一个特殊的节点被挑选出来,被称为树的“根”,并且从根到每个其他节点都有唯一的路径。
Bob打算用笔来着色树的所有节点。一棵树有n个节点,这些节点编号为1, 2,…,n。假设一个节点着色需要1个单位时间,并且在完成一个节点着色之后,允许他对另一个节点着色。另外,只有当父节点被着色时,才允许他对节点着色。显然,Bob只允许在第一次尝试中着色根。
每个节点都有一个“着色成本因子”,Ci。每个节点的着色成本取决于Ci和Bob完成该节点着色的时间。开始时,时间设置为0。如果着色节点i的完成时间是FI,则节点I的着色代价是Ci*Fi。
例如,在图1中示出了一个具有五个节点的树。每个节点的着色成本因子分别为1,2,1,2和4。Bob可以以1,3,5,2,4的顺序对树进行着色,最小总着色成本为33。

给定一个树和每个节点的着色代价因子,请帮助Bob找到着色所有节点的最小可能的总着色代价。
输入格式
无
输出格式
无