记录编号	49081	评测结果	APPPP
题目名称	小树	最终得分	95
用户昵称	怡红公子	是否通过	未通过
代码语言	C++	运行时间	0.006 s
提交时间	2012-11-07 12:23:38	内存使用	3.18 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<fstream>
using namespace std;
//ifstream fin("treec.in");
//ofstream fout("treec.out");

int T,n;
int head[1005],edgs=0;
struct{int u,v,w,next;}edg[1005];
int h[1005]={0},d[1005]={0};

void Addedg(int u,int v,int w){
     edgs++;
     edg[edgs].u=u;edg[edgs].v=v;edg[edgs].w=w;
     edg[edgs].next=head[u];
     head[u]=edgs;
     }

void Dfs(int last){
     for(int i=head[last];i!=-1;i=edg[i].next)
     {
       int u=edg[i].u,v=edg[i].v,w=edg[i].w;
       h[v]=h[last]+w;
       d[v]=d[last]+1;
       Dfs(v);
             }
     }

double f[1005]={0};
double Dp(int k){
    if(f[k]!=0) return f[k];
    double ma=0;
    if(k!=0) ma=h[k]/(d[k]*1.0);
    for(int i=head[k];i!=-1;i=edg[i].next)
    {
      int v=edg[i].v;
      double dd=Dp(v);
      if(dd>ma) ma=dd; 
            }
    f[k]=ma;
    return f[k];
    }

int main()
{
    freopen("treec.in","r",stdin);
    freopen("treec.out","w",stdout);
    scanf("%d",&T);//fin>>T;
    while(T>0)
    {
      T--;
      edgs=0;
      memset(f,0,sizeof(f));
      memset(h,0,sizeof(h));
      memset(d,0,sizeof(d));
      memset(head,-1,sizeof(head));
      scanf("%d",&n);//fin>>n;
    
      for(int i=1;i<n;++i)
      {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);//fin>>u>>v>>w;
        Addedg(u,v,w);
              }
      Dfs(0);
      
   //   for(int i=0;i<n;++i)
   //   cout<<h[i]<<"  "<<d[i]<<endl; 
    
      printf("%.2f\n",Dp(0));        
              }
    
    //cout<<Dp(0)<<endl;
  //  system("pause");
    return 0;
    
    }