比赛 20121107 评测结果
题目名称 小树 最终得分 65
用户昵称 Vow Ryan 运行时间 0.029 s
代码语言 Pascal 内存使用 7.97 MiB
提交时间 2012-11-07 10:53:51
显示代码纯文本
var
 a,w:array[0..1010,0..1010]of longint;
 dep,d,cnt:array[0..1010]of longint;
 i,j,k,l,m,n,p,t,x:longint;
 ans,temp:double;
 
procedure init;
 begin
  for i:=1 to 1010 do a[i,0]:=0;
  fillchar(dep,sizeof(dep),0);
  fillchar(d,sizeof(d),0);
  fillchar(cnt,sizeof(cnt),0);
  m:=0;ans:=0;
  read(n);
  for i:=1 to n-1 do
   begin
    read(j,k,l);
    inc(a[j,0]);
    a[j,a[j,0]]:=k;
    w[j,a[j,0]]:=l;
   end;
 end;
 
procedure build(u:longint);
 var
  i:longint;
 begin
  for i:=1 to a[u,0] do
   begin
    dep[a[u,i]]:=dep[u]+1;
    d[a[u,i]]:=d[u]+w[u,i];
    if u=0 then 
     if ans<d[a[u,i]]/dep[a[u,i]] then ans:=d[a[u,i]]/dep[a[u,i]];
    build(a[u,i]);
   end;
 end;

procedure count(u:longint);
 var
  j:longint;
 begin
  if d[u]/dep[u]>d[cnt[i]]/dep[cnt[i]] then cnt[i]:=u;
  for j:=1 to a[u,0] do count(a[u,j]);
 end;

begin
 assign(input,'treec.in');reset(input);
 assign(output,'treec.out');rewrite(output);
 readln(t);
 for p:=1 to t do
  begin
   init;
   build(0);
   for i:=1 to a[0,0] do
    begin
     x:=a[0,i];
     cnt[i]:=x;
     count(x);
    end;
   for i:=1 to a[0,0]-1 do
    for j:=i+1 to a[0,0] do
     begin
      temp:=(d[cnt[i]]+d[cnt[j]])/(dep[cnt[i]]+dep[cnt[j]]);
      if ans<temp then ans:=temp;
     end;
   writeln(ans:0:2);
  end;
 close(input);close(output);
end.