//求测试数据， 2天了，xxxxxxxxxxxxxxxxx谢
#include<iostream>
using namespace std;

int c[1010], pre[1010], next[1010];

double c1[1010];
int n, r;
int findmax(double c1[])//非r的最大节点
{
	int i, th;
	double max;
	max = 0;
	th = 0;
	for(i = 1; i <= n; i++)
	{
		if(c1[i] > max && i != r)
		{
			max = c1[i];
			th = i;
		}
	}
	return th;
}

void uni(int d, int pred)
{
	int i;
	for(i = 1; i <= n; i++)
		if(pre[i] == d)
			pre[i] = pred;
	if(pred != r)
		c1[pred] = (c1[d] + c1[pred])/2;
	c1[d] = 0;
	for(i = pred; next[i] != 0; i = next[i]);

	next[i] = d;

}

int main()
{
	int i, d, e, sum;
	cin>>n>>r;

	while(n || r)
	{
		pre[r] = r;
		memset(next, 0, sizeof(next));
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &c[i]);
			c1[i] = c[i];
		}
		for(i = 1; i < n; i++)
		{
			scanf("%d%d", &d, &e);
			pre[e] = d;
		}
		for(i = 1; i < n; i++)
		{
			d = findmax(c1);
			uni(d, pre[d]);
		}
		sum = 0; 
		d = 1;
		for(i = r; i != 0; i = next[i])
		{
			sum += d*c[i];
			d++;
		}
		cout<<sum<<endl;

		cin>>n>>r;
	}
	return 0;
}

• Re:求测试数据， 2天了，xxxxxxxxxxxxxxxxx谢 (20) WarTalker 2008-09-08 14:00:07
• Re:求测试数据， 2天了，xxxxxxxxxxxxxxxxx谢 (1246) 142601 2009-08-22 09:13:43
• Re:求测试数据， 2天了，xxxxxxxxxxxxxxxxx谢 (1246) 1982127876 2016-08-27 15:07:36