这次是把排序的标准改了
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct pi
{
	int c,id;
}p[1010],t[1010],ss[1010];

int f[1010],pt[1010];
int v[1010];

int cmp (const void *a,const void *b)
{
	return ((struct pi *)a)->c - ((struct pi *)a)->c;
}

int main ()
{
	int n,r,i,cnt,cn,sum,fa,sn,tmp,ts;
	while (scanf ("%d%d",&n,&r) && (n || r))
	{
		memset (p,0,sizeof (p));
		memset (t,0,sizeof (t));
		memset (f,0,sizeof (f));
		memset (pt,0,sizeof (pt));
		memset (v,0,sizeof (v));

		for (i=1;i<=n;i++)
		{
			scanf ("%d",&p[i].c);
			p[i].id=i;
		}
		memcpy (ss,p,sizeof (p));
		for (i=1;i<n;i++)
		{
			scanf ("%d%d",&fa,&sn);
			f[sn]=fa;
		}
		for (i=1;i<=n;i++)
		{
			tmp=i;
			cnt=cn=0;
			while (tmp)
			{
				cnt+=p[tmp].c;
				cn++;
				tmp=f[tmp];
			}
			t[i]=p[i];
			t[i].c=(int)(cnt/cn);
		}

		memcpy (p,t,sizeof (t));
		qsort (&p[1],n,sizeof (p[0]),cmp);

		cn=0;
		for (i=n;i>=1;i--)
			if (v[p[i].id]==0)		
			{
				tmp=p[i].id;
				cnt=cn;
				while (tmp>0)
				{
					if (v[tmp]==0) cnt++;
					else break;
					tmp=f[tmp];
				}
				tmp=p[i].id;
				cn=cnt;
				while (tmp>0)
				{
					if (v[tmp]==0)
					{
						v[tmp]=1;
						pt[cnt]=tmp;
						cnt--;
					}
					else break;
					tmp=f[tmp];
				}
			}
		sum=0;
		for (i=1;i<=n;i++)
			sum+=i*ss[pt[i]].c;
		printf("%d\n",sum);
	}
	return 0;
}

• Re:color a tree (why my mathod is wrong?) another one but still wa (177) cxf476 2006-04-02 19:33:02