记录编号	49388	评测结果	AAAAA
题目名称	小树	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-11-07 19:35:23	内存使用	2.93 MiB

#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
using namespace std;
ifstream fin("treec.in");
ofstream fout("treec.out");
int T,N;
double Ans,S;
class Node
{
public:
	int name;
	double weight;
	Node *Prev;
}*last[100001];
void Add(int u,int v,int w)
{
Node *temp=new Node;
	temp->name=v;temp->weight=w;temp->Prev=last[u];
	last[u]=temp;
}
void DFS(int pos,double Wi,double Di)
{
Node *temp;
	S=max(S,Wi/Di);
	for(temp=last[pos];temp;temp=temp->Prev)
		DFS(temp->name,Wi+temp->weight,Di+1);
}
int main()
{
int i,j;
	for(i=0;i<=100000;i++)
		last[i]=NULL;
	fin>>T;
	for(i=1;i<=T;i++)
	{
		fin>>N;
		for(j=0;j<N;j++)
			while(last[j]!=NULL)
			{
			Node *temp=last[j]->Prev;
				free(last[j]);
				last[j]=temp;
			}
		//initialize
		for(j=1;j<N;j++)
		{
		int U,V,W;
			fin>>U>>V>>W;
			Add(U,V,W);
		}
		//read
		Ans=0.0;
		for(Node *temp=last[0];temp;temp=temp->Prev)
		{
			S=0;
			DFS(temp->name,temp->weight,1.0);
			Ans=max(Ans,S);
		}
		
		fout<<setiosflags(ios::fixed)<<setprecision(3)<<Ans<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}