[poj2054]Color a Tree

 1 #include<cstdio>
 2 #define N 1005
 3 int n,r,x,y,ans,a[N],f[N],sz[N];
 4 int main(){
 5     while (scanf("%d%d",&n,&r)!=EOF){
 6         if ((!n)&&(!r))return 0;
 7         ans=0;
 8         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 9         for(int i=1;i<=n;i++)ans+=a[i];
10         for(int i=1;i<=n;i++)sz[i]=1;
11         for(int i=1;i<n;i++){
12             scanf("%d%d",&x,&y);
13             f[y]=x;
14         }
15         for(int i=1;i<n;i++){
16             x=0;
17             for(int j=1;j<=n;j++)
18                 if ((j!=r)&&((!x)||(a[x]*sz[j]<a[j]*sz[x])))x=j;
19             y=f[x];
20             ans+=sz[y]*a[x];
21             for(int j=1;j<=n;j++)
22                 if (f[j]==x)f[j]=y;
23             f[x]=y;
24             a[y]+=a[x];
25             a[x]=0;
26             sz[y]+=sz[x];
27         }
28         printf("%d\n",ans);
29     }
30 }