一棵树，结点树为n，根结点为r。每个结点都有一个权值ci，开始时间为0，每染色一个结点需要耗时1，
每个结点的染色代价为ci*ti（ti为当前的时间），
每个结点只有在父结点已经被染色的条件下才能被染色。
求染完整棵树需要花费的最小代价。
找出当前最大子节点和其父节点合并成新的节点
直到点集中只剩一个节点
因为合并时将子节点的权值加在父节点上
则 每次更新 答案加上当前子节点的权值乘上父节点的花费时间，这个很神奇
因为合并后，当对其父节点操作时也会重复加上子节点权值，
即累加起来等同于每一个节点的最初权值乘上对应时间
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct node{
int f,v,t;
double w;//权值
}p[];
int n,r,a,b;
int main()
{
while(~scanf("%d%d",&n,&r),n+r)
{
int ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&p[i].v);
p[i].w=p[i].v;
p[i].t=;
ans+=p[i].v;
}
for(int i=;i<n;i++)
{
scanf("%d%d",&a,&b);
p[b].f=a;
}
double wmax;
int pos,fa;
for(int i=;i<n;i++)
{
wmax=-;
for(int j=;j<=n;j++)//找当前大子节点
{
if(j==r) continue;//子节点！
if(wmax<p[j].w)//点权值比较时对比算数平均值
{
wmax=p[j].w;
pos=j;
}
}
p[pos].w=-;//去掉子节点
fa=p[pos].f;
ans+=p[pos].v*p[fa].t;//更新答案
for(int j=;j<=n;j++)//将子节点的子节点全部接在新建节点上
if(p[j].f==pos) p[j].f=fa;
p[fa].v+=p[pos].v;//新节点在父节点位置，节点的总权值等同于父子权值和
p[fa].t+=p[pos].t;//个数
p[fa].w=1.0*p[fa].v/p[fa].t;//比较时权值等于算术平均值
}
printf("%d\n",ans);
}
}