Color a Tree
题意：每个节点有一个权值，从根节点开始着色，每一个被着色的节点，其父亲一定已经被着色了，根据着色顺序得到一个序列，求最小的序列对应的权值的乘积和最小；
分析：寻找最大权值，合并这个节点和他的父亲节点，记下这两个节点的拓扑序列，同时新节点的权值为这些节点的算术平均值，直到只有一个节点。
证明：
http://hi.baidu.com/cheezer94/blog/item/d98eca065202a2f237d122da.html
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
double v[1010];
int num[1010],q[1010];
bool cmp(int a,int b)
{
return v[a]/num[a]>v[b]/num[b];
}
int ff[1010],ss[1010],fa[1010];
int n,r,val[1010];
int farther(int i)
{
if(ff[i]==i)return i;
return ff[i]=farther(ff[i]);
}
int son(int i)
{
if(ss[i]==i)return i;
return son(ss[i]);
}
bool input()
{
scanf("%d%d",&n,&r);
if(n==0&&r==0)return 0;
int i,f,s;
r--;
for(i=0;i<n;i++)
{
scanf("%d",&val[i]);
fa[i]=ff[i]=ss[i]=q[i]=i;
num[i]=1;v[i]=val[i]*1.0;
}
for(i=1;i<n;i++)
{
scanf("%d%d",&f,&s);
fa[s-1]=f-1;
}
return 1;
}
void solve()
{
int ans=0,k=1,i,now,t;
for(i=0;i<n;i++)//取出比值最大的没被访问的点。
{
sort(q+i,q+n,cmp);
now=q[i];t=son(fa[now]);
if(now==r)continue;
ss[t]=now;ff[now]=t;
t=farther(now);
v[t]+=v[now];num[t]+=num[now];
}
while(n--)
{
ans+=val[r]*(k++);
r=ss[r];
}
printf("%d\n",ans);
}
int main()
{
while(input())solve();
return 0;
}
