http://acm.hdu.edu.cn/showproblem.php?pid=1055&&Color a Tree

　这道题整了一下午，最后还是看别人的解题报告弄出来的，先说说我的理解吧。大体处理思路是利用贪心思想，每次取权值最大的节点，不断的将权值最大节点与它的父节点合并。

过程：

1、初始时将序列中的time[i]都置为1，w[i]置为c[i]；

2、查找最大的w[i]， 返回其位置；

3、将该位置的c[]与它的父节点c[]合并（合并过程就是C_i / T_i，C_i = c[该节点] + c[父节点]，T_i = time[该节点]+time[父节点]）得到新的父节点w[]（w[父节点] = C_i / T_i），如果有节点与pos相连，让它指向pos的父节点；

4、重复2、3，知道合并完；

至于如何求出结果：初始时使ans = sum(c[i])；每次查找到一个最大权值，ans += c[i] * time[父节点]；

具体代码如下：

#include<iostream>
#include<algorithm>
#define N  10001
using namespace std;
typedef struct{
	 int c;
	 int t;
	 double w;
	 int p;
}Node;
int n,r;
Node s[N];
int f()
{   double max=-123343.0;
     int pos=1,i;
	for(i=1;i<=n;++i)
	 if(s[i].w>max&&i!=r)
	 {max=s[i].w;pos=i;}
	return pos;
 }
int main()
{ while(cin>>n>>r&&n&&r)
  {  int ans=0;
	  for(int i=1;i<=n;++i)
      { cin>>s[i].c;
         s[i].w=s[i].c;
		 s[i].t=1;
		 ans+=s[i].c;
       }
      for(int j=1;j<n;++j)
	  { int a,b;
	     cin>>a>>b;
		 s[b].p=a;
	  }
	  int k=n;
	  while(k>1)
	  {  int pos=f();
	       s[pos].w=0;
	      int f=s[pos].p;
		   ans+=s[pos].c*s[f].t;
		   for(int i=1;i<=n;++i)
			   if(s[i].p==pos) s[i].p=f;
		   s[f].t+=s[pos].t;
		   s[f].c+=s[pos].c;
		   s[f].w=(double)s[f].c/s[f].t;
		   k--;
	  }
	  cout<<ans<<endl;
    }return 0;
 }