记录编号	49092	评测结果	AAAAA
题目名称	小树	最终得分	100
用户昵称	剑舞江南	是否通过	通过
代码语言	Pascal	运行时间	0.008 s
提交时间	2012-11-07 12:42:45	内存使用	0.19 MiB

Program PP3;
Var qi,mo,zh,f,q,d,w:array[0..1010]of longint;
    t,l,n,a,b,c,xx,head,tail,i:longint;
    max,k:real;
Procedure qsort(s,t:longint);
  var i,j,mid,temp:longint;
  begin
  i:=s; j:=t; mid:=qi[(s+t)div 2];
  while i<=j do
    begin
      while qi[i]<mid do inc(i);
      while qi[j]>mid do dec(j);
      if i<=j then
        begin
        temp:=qi[i]; qi[i]:=qi[j]; qi[j]:=temp;
        temp:=mo[i]; mo[i]:=mo[j]; mo[j]:=temp;
        temp:=zh[i]; zh[i]:=zh[j]; zh[j]:=temp;
        inc(i); dec(j);
        end;
    end;
  if i<t then qsort(i,t);
  if j>s then qsort(s,j);
  end;
Begin
assign(input,'treec.in'); reset(input);
assign(output,'treec.out'); rewrite(output);
  readln(t);
  for l:=1 to t do begin
    readln(n);
    if n=1 then writeln('0.00');
    if n<>1 then begin
      max:=0;
      fillchar(qi,sizeof(qi),0);
      fillchar(mo,sizeof(mo),0);
      fillchar(zh,sizeof(zh),0);
      fillchar(f,sizeof(f),0);
      for i:=1 to n-1 do begin
        readln(a,b,c);
        qi[i]:=a; mo[i]:=b; zh[i]:=c;
      end;
      qsort(1,n-1);
      f[qi[1]]:=1; f[n]:=n;
      for i:=2 to n-1 do
        if qi[i]<>qi[i-1] then f[qi[i]]:=i;
      for i:=n-1 downto 1 do
        if f[i]=0 then f[i]:=f[i+1];
      fillchar(q,sizeof(q),0);
      fillchar(d,sizeof(d),0);
      fillchar(w,sizeof(w),0);
      q[1]:=0; d[0]:=0; w[0]:=0;
      head:=0; tail:=1;
      while head<tail do begin
        inc(head); xx:=q[head];
        for i:=f[xx] to f[xx+1]-1 do begin
          d[mo[i]]:=d[xx]+1;
          w[mo[i]]:=w[xx]+zh[i];
          k:=w[mo[i]]/d[mo[i]];
          if k>max then max:=k;
          inc(tail);
          q[tail]:=mo[i];
        end;
      end;
      writeln(max:0:2);
    end;
  end;
close(input);
close(output);
End.