题意：一棵有(n(1≤n≤1000))个节点的树，每个节点(i(1≤i≤n))都有一个权值(a_i).现在要把这棵树的节点全部染色，染色的规则是：根节点(root)可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色.每次染色的代价为(T*a[i])，其中 (T) 代表当前是第几次染色.求把这棵树染色的最小总代价.
分析：贪心策略：权值最大的点及其父亲节点的染色是连续进行的，即权值最大的点在它的父亲染色后一定会立即染色。所以我们可以考虑合并这两个点，合并得到的新点的权值为这两个点的平均值.所以我们不断地在树上取权值最大的点，然后与其父亲节点合并，同时计算代价即可.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1005;
int a[N],fa[N],size[N],visit[N];
int tot,head[N],nxt[N*2],to[N*2];
inline void add(int a,int b){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;}
inline int find(int n,int root){
int node;double maxn=0.0;
for(int i=1;i<=n;++i)
if(!visit[i]&&i!=root&&maxn<(double)a[i]/size[i]){
maxn=(double)a[i]/size[i];node=i;
}
return node;
}
inline void Union(int pre,int node){
a[pre]+=a[node];size[pre]+=size[node];
for(int i=head[node];i;i=nxt[i])fa[to[i]]=pre;
}
inline int solve(int n,int root){
int ans=0;
for(int i=1;i<n;++i){//记得只要n-1次
int node=find(n,root);//找到平均权值最大的点
visit[node]=1;
int pre=fa[node];
while(visit[pre])pre=fa[pre];//找到该点的父亲节点
ans+=a[node]*size[pre];//计算代价
Union(pre,node);//合并
}
return ans+a[root];
}
int main(){
while(1){
int n=read(),root=read();if(!n&&!root)break;
tot=0;memset(head,0,sizeof(head));memset(visit,0,sizeof(visit));
for(int i=1;i<=n;++i)a[i]=read(),size[i]=1;
for(int i=1;i<n;++i){
int x=read(),y=read();
add(x,y);fa[y]=x;
}
printf("%d
",solve(n,root));
}
return 0;
}