#894. [POJ2054] Color a Tree 给树染色
[POJ2054] Color a Tree 给树染色
题目描述
一颗树有 n 个节点,这些节点被标号为:1, 2, 3, …, n,每个节点 i 都有一个权值 A[i]。
现在要把这棵树的节点全部染色,染色的规则是:
每次只能选择一个节点对其进行染色;
根节点 R 可以随时被染色;
对于其他节点,在被染色之前它的父亲节点必须已经染上了色。
对节点 i 染色的代价为 T×A[i],其中 T 代表当前是第几次染色,即节点 i 是第几个被染色的节点。
求把这棵树的节点全部染色的最小总代价。
输入格式
第一行包含两个整数 n 和 R,分别代表树的节点数以及根节点的序号。
第二行包含 n 个整数,代表所有节点的权值,第 i 个数即为第 i 个节点的权值 A[i]。
接下来 n-1 行,每行包含两个整数 a 和 b,代表两个节点的序号,两节点满足关系: a 节点是 b 节点的父节点。
除根节点外的其他 n-1 个节点的父节点和它们本身会在这 n-1 行中表示出来。
同一行内的数用空格隔开。
输出格式
输出一个整数,代表把这棵树染色的最小总代价。
数据范围
1≤n≤1000, 1≤A[i]≤1000
输入样例
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
输出样例
33