记录编号	49227	评测结果	APPPP
题目名称	小树	最终得分	95
用户昵称	ACdog	是否通过	未通过
代码语言	C	运行时间	0.006 s
提交时间	2012-11-07 15:18:23	内存使用	0.32 MiB

#include<stdio.h>
int T,n,first[1001],next[1001],v[1001];
double w[1001],f[1001];
int dfs(int i,double d,double s);
int main()
{
	FILE *in=fopen("treec.in","r");
	FILE *out=fopen("treec.out","w");
	int i,k,t;
	fscanf(in,"%d",&T);
	for(k=1;k<=T;k++)
	{
		fscanf(in,"%d",&n);
		for(i=0;i<n;i++)
		{
			first[i]=-1;
			f[i]=-0x7fffffff;
			}
		f[0]=0;
		for(i=1;i<n;i++)
		{
			fscanf(in,"%d %d %lf",&t,&v[i],&w[i]);
			next[i]=first[t];
			first[t]=i;
			}
		for(i=first[0];i!=-1;i=next[i])
		{
			dfs(v[i],1,w[i]);
			if(f[v[i]]>f[0])
				f[0]=f[v[i]];
			}
		fprintf(out,"%.2lf\n",f[0]);	
		}
	return 0;
	}
int dfs(int i,double d,double s)
{
	int x=first[i];
	while(x!=-1)
	{
		dfs(v[x],d+1,s+w[x]);
		x=next[x];
		}
	x=first[i];
	while(x!=-1)
	{
		if(f[v[x]]>f[i])
		f[i]=f[v[x]];
		x=next[x];
		}	
	if(s/d>f[i])
		f[i]=s/d;
	return 0;
	}