思路yxc大佬已经讲得很清楚啦,这里是一点小优化,利用并查集和大根堆(STL priority_queue)将时间复杂度从$O(n^2)$降至$O(nlogn)$

一些要注意的细节:
1. 节点是有可能重复入队的,又因节点的“合并权值”实时更新,所以当它被取出来的时候只需要判重且用它最新的权值即可
2. 记得重置fa数组和vis数组,这是一道多组输入的题目(UVA原题是这样的)
3. 祖先节点是不能入队的,一定要加以判断(因为它不能合并了)

#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int maxn=1000+10;
struct node
{
    int f,s,v;//father,size,value
}a[maxn];
int n,R;
int fa[maxn];
bool vis[maxn];
priority_queue<pair<double, int> >q;

int get(int x) {return fa[x]=fa[x]==x?x:get(fa[x]);}//表示合并之后的祖先节点,可以代表合并之后的集合
int main()
{
    while(scanf("%d%d",&n,&R)&&n&&R)
    {
      int ans=0;
      for (int i=1;i<=n;i++)
      {
          scanf("%d",&a[i].v);
          a[i].s=1;
          ans+=a[i].v;
          if (i!=R)
              q.push(make_pair(a[i].v, i));
      }
      for (int i=1;i<=n-1;i++)
      {
          int u,v;
          scanf("%d%d",&u,&v);
          a[v].f=u;
      }
      for (int i=1;i<=n;i++)
          fa[i]=i,vis[i]=0;
      while(!q.empty())
      {
          int p=q.top().second;
          q.pop();
          if (vis[p])//有可能会重复入队,所以要加以判断
              continue;
          vis[p]=1;
          int f=get(a[p].f);
          ans+=a[f].s*a[p].v;
          a[f].v+=a[p].v;
          a[f].s+=a[p].s;
          if (f!=R)
              q.push(make_pair((double)a[f].v/a[f].s, f));//新合并的点入队
          fa[p]=f;//更新祖先节点
      }
      printf("%d\n",ans);
    }
    return 0;
}