题目概述
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。
输入输出格式
输入格式：
输入由几个测试数据组成。每一行的第一行包含两个整数 n 和 r （1＜n<＝1000, 1 <＝r <＝n），其中 n 是树中的节点数，r 是根节点的节点数。第二行包含 n 个整数，其中第 i 个是 Ci（1＜Ci＝500），节点 i 的着色代价因子 l 。每个下一个 N-1 行包含两个空间分离的节点编号 V1 和 V2 ，它们是树中的边的端点，表示 V1 是 V2 的父节点。
没有边将被列出两次，所有的边将被列出。
n＝0 和 r＝0 的测试样例表示输入的结束，不应该被处理。
输出格式：
对于每个测试样例，输出一个包含 Bob 所需的最小总着色代价的行，以对所有节点着色。
样例输入
5 1
1 2 1 1 2 4
1 2
1 3
2 4
3 5
0 0
样本输出
33
Color a Tree: 原题看这里
思路解析
整体思路
看到这道题，首先会出现一个错误的贪心思路----“每一步在可以被染色的点里选权值最大的染色”。这个思路的反例很容易给出----“构造一棵树，让一个权值很小的结点下面有很多权值巨大的结点，另一个权值较大的结点却没有子结点”。
但是我们可以从这个错误的贪心思路里提取出一个正确的性质：树中除根节点外权值最大的点，一定会在它的父节点被染色后立即染色。
于是我们可以确定，树中权值最大的点及其父节点的染色操作是连续进行的，我们可以把这两个点合并起来，合并后的点的权值为二者平均值。
（具体见后–等效权值算法）
我们不断在树中提取“等效权值”最大的点或点集 p ，p 再与其父节点合并，最后整棵树合并到一个点后（即根节点），我们便可算出各结点染色顺序以及总代价。
等效权值 算法
假如有权值为 x，y，z 的三个点，我们已知 x 和 y 的染色操作是连续的，那么就有两种可能的染色方案：
1、先染 x，y，再染 z ，代价是 x + 2 y + 3 z
2、先染 z，再染 x，y， 代价是z + 2 x + 3 y
我们在两个式子同时加上 z - y ，再除以 2，分别得到：
1、代价 （x + y）/ 2 + 2 * z
2、代价 z + 2 *（（x + y）/ 2）
这就相当于有权值 （x + y）/ 2 和 z 的两个点的两种染色顺序。换言之，下列两种情况的“最优染色次序”可以相互转化：
1、权值为 x，y，z 的三个点
2、权值为 （x + y）/ 2 和 z 的两个点
由此我们得到一种“等效权值”的算法：
点集的权值 =（该点集包含的原始权值总和） / （该点集包含的原始点数）
代价和 算法
我们可以把结点类比为在队列里等待的顾客。
对于两个点（集），设点（集） x 和 x.pre ，设立 fact 数组记录这群人每分产生的代价值（点集中权值和），num 数组记录这群人让后面的人又等了几分钟（点集中点的数量）。
当 x 要 与 x.pre 合并时，ans += fact[x] * num[x.pre]，意思是 x 中的人又要多等 num[x.pre] 分钟，会增加 fact[x] * num[x.pre] 的不满意值。
以样例输入为例：
先初始化fact[i]=Ci, num[i]=1;将每一个点看成一个集合。
按照贪心原则首先选择5合并到3形成集合A={3,5}，
fact[A]=5,num[A]=2;
Ans+=fact[5]*num[3]=4；
然后再按照贪心原则选择集合A合并到1形成集合B={1,3,5}，fact[B]=6,num[B]=3;
Ans+=fact[A]*num[1]=9;
然后再选择2合并到集合B形成集合C={1,2,3,5}，
fact[C]=8, num[C]=4;
Ans+=fact[2]*num[B]=15;
最后选择4合并到集合C形成集合D={1,2,3,4,5}，
fact[D]=10,num[D]=5;
Ans+=fact[4]*num[C]=23;
最后Ans+=fact[D]=33;
代码实现
#include<iostream>
using namespace std;
struct Node
{
int cost; // 代价因子
int id; // 结点编号
int pre = 0; // 父结点id
}node[1000];
double fact[1000];
double num[1000];
int visit[1000] = { 0 };
// 寻找最大值的结点或点集
int find(int N,int root)
{
double max = 0;
int pos = 1;
for (int i = 1; i <= N; i++)
{
if (!(visit[i]) && (double)(fact[i] / num[i]) > max && i != root)
{
pos = i;
max = (double)(fact[i] / num[i]);
}
}
return pos;
}
void main()
{
// 树的结点数, 根结点id
int N, R;
cin >> N >> R;
for (int i = 1; i <= N; i++)
{
node[i].id = i;
cin >> node[i].cost;
num[i] = 1;
fact[i] = node[i].cost;
}
// 输入0结束
int fa = 1; int s = 1;
while (fa || s)
{
cin >> fa >> s;
node[s].pre = fa;
}
int max_w_pos = 0;
int pre = 0;
int ans = 0;
for (int i = 1; i <= N ; i++)
{
// 最大权值的位置
max_w_pos = find(N, R);
//cout << "maxpos=" << max_w_pos << endl;
visit[max_w_pos] = 1;
pre = node[max_w_pos].pre;
while (visit[pre])
pre = node[pre].pre;
//cout << "pre=" << pre << endl;
ans += fact[max_w_pos] * num[pre];
fact[pre] += fact[max_w_pos];
num[pre] += num[max_w_pos];
}
ans += fact[pre];
cout << ans << endl;
}