记录编号	49205	评测结果	PPPPP
题目名称	小树	最终得分	32
用户昵称	极寒之魇	是否通过	未通过
代码语言	Pascal	运行时间	0.112 s
提交时间	2012-11-07 14:58:16	内存使用	4.13 MiB

uses math;
type point=^node;
     node=record
      ve:longint;
      next:point;
      data:longint;
     end;
var a:array[0..1000] of node;
    f:array[1..1000000] of longint;
    v:array[0..1000] of boolean;
    dis:array[0..1000]of longint;
    mo:array[0..1000] of longint;
    i,n,t,j:longint;
    ans:real;

procedure init;
  var x,y,z,i:longint;
      p:point;
  begin
   for i:=1 to n do
   begin new(p); a[i].ve:=0; a[i].next:=nil; a[i].data:=0; end;
   for i:=1 to n-1 do
   begin readln(x,y,z);
         new(p); a[x].ve:=x; p^.ve:=y; p^.next:=a[x].next; a[x].next:=p; p^.data:=z;
   end;
   end;

procedure spfa;
  var head,tail,now:longint;
      p:point;
  begin
  fillchar(v,sizeof(v),false);
  fillchar(dis,sizeof(dis),$7f);
  fillchar(mo,sizeof(mo),0);
  fillchar(f,sizeof(f),0);
  head:=0; tail:=1; f[1]:=a[0].ve;
  v[f[1]]:=true; dis[0]:=0;
  while head<>tail do
  begin
  inc(head); head:=head mod 1000000; now:=f[head];
  p:=a[now].next;
  while p<>nil do
  begin
  if dis[p^.ve]>dis[now]+p^.data then begin
     dis[p^.ve]:=dis[now]+p^.data;
     mo[p^.ve]:=mo[now]+1;
     if not v[p^.ve] then begin inc(tail); tail:=tail mod 1000000;
                                  f[tail]:=p^.ve; v[f[tail]]:=true; end;
     end;
     p:=p^.next;
     end;
     v[f[head]]:=false;
     end;
     end;

begin
  assign(input,'treec.in'); reset(input);
  assign(output,'treec.out'); rewrite(output);
  readln(t);
  for i:=1 to t do
  begin
  ans:=0;
  readln(n);
  if n=1 then begin writeln(ans:0:2); continue; end;
  init;
  spfa;
  for j:=1 to n-1 do
  ans:=max(ans,dis[j]/mo[j]);
  writeln(ans:0:2);
  end;
  close(output);
end.