题目链接：Click here

Solution:

看起来不太能dp，则考虑树上贪心

题目要求一个点必须先染父亲才能染自己，就给了我们启示，贪心的合并点

我们定义一个点的权重为这个点的价值和/点数，然后贪心的选择权重最大的点加入到答案，合并到他的父亲

值得注意的是加入到答案的过程为加上这个点的价值和\(\times\)父亲节点的点数，因为这代表在他之前染色的点数

Code：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,root;

struct node{

	int s,v,f;

	double w;

}tree[1001];

int find_max(){

	int m;double maxn=0;

	for(int i=1;i<=n;i++)

		if(i!=root&&tree[i].w>maxn)

			maxn=tree[i].w,m=i;

	return m;

}

int main(){

	while(1){

		scanf("%d%d",&n,&root);

		if(n==0&&root==0)break;

		int ans=0;

		for(int i=1;i<=n;i++){

			scanf("%d",&tree[i].v);

			tree[i].s=1;tree[i].w=double(tree[i].v);

			ans+=tree[i].v;

		}

		for(int i=1;i<n;i++){

			int a,b;scanf("%d%d",&a,&b);

			tree[b].f=a;

		}

		for(int i=1;i<n;i++){

			int now=find_max();

			int fa=tree[now].f;

			ans+=tree[now].v*tree[fa].s;

			tree[now].w=0;

			for(int j=1;j<=n;j++)

			if(tree[j].f==now)tree[j].f=fa;

			tree[fa].s+=tree[now].s;

			tree[fa].v+=tree[now].v;

			tree[fa].w=double(tree[fa].v)/tree[fa].s;

		}printf("%d\n",ans);

	}

	return 0;

}