记录编号	49073	评测结果	AAAAA
题目名称	小树	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2012-11-07 12:12:58	内存使用	3.17 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int t,n,a,b,v;
double answer=0,ans=0;
vector<int>con[1005];
vector<int>val[1005];
bool used[1005];
void dfs(int x,int y);
int main()
{
	freopen ("treec.in","r",stdin);
	freopen ("treec.out","w",stdout);
	cin>>t;
	for (int o=0;o<t;o++)
	{
		cin>>n;
		if (n==1)
		{
			cout<<"0.00"<<endl;
			continue;
		}
		for (int i=0;i<n;i++)
		{
			used[i]=0;
			con[i].clear();
			val[i].clear();
		}
		for (int o=1;o<n;o++)
		{
			cin>>a>>b>>v;
			con[a].push_back(b);
			con[b].push_back(a);
			val[a].push_back(v);
			val[b].push_back(v);
		}
		answer=0;
		ans=0;
		used[0]=1;
		dfs(0,0);
		printf("%.6lf\n",answer);
	}
	return 0;
}
void dfs(int x,int y)
{
	if (y!=0)
	{
		if (((double)ans/y)>answer)
			answer=((double)ans/y);
	}
	for (int i=0;i<con[x].size();i++)
	{
		if (!used[con[x][i]])
		{
			used[con[x][i]]=1;
			ans+=val[x][i];
			dfs(con[x][i],y+1);
			ans-=val[x][i];
		}
	}
}