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找到着色所有节点的最小可能的总着色代价。

无

无