记录编号	9875	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 184] 洞窟探索	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	0.372 s
提交时间	2009-04-21 21:08:47	内存使用	14.45 MiB

program hole;
 const
    Inf=1000000000;
    maxn=1500; maxm=1000;
  var
      n,m:      longint;
      son:      array[1..maxn] of longint;
      visit:    array[1..maxn] of boolean;
      l:        array[1..maxn,0..2] of longint;
      g:        array[1..maxn,1..maxn] of longint;
      opt:      array[0..maxn,0..maxm] of longint;
      Ans:      longint;


 procedure built(v:longint);
   var
       i:       longint;
   begin
     visit[v] :=true;
     for i :=1 to n do if g[v,i]>0
         then begin
              if visit[i] then continue;
              inc(l[v,0]); l[v,l[v,0]]:=i;
              built(i);    inc(son[v],son[i]);
              end;
     inc(son[v]);
   end;


 procedure Init;
   var
      i,x,y,u:        longint;

  begin
    readln(n,m);
    for i :=1 to n-1 do begin
        readln(x,y,u);
        g[x,y] :=u;
        g[y,x] :=u;
        end;
    built(1);
  end;

 function min(a,b:longint):longint;

   begin
     if a<b then exit(a) else exit(b);
   end;

 function max(a,b:longint):longint;

   begin
     if a>b then exit(a)  else exit(b);
   end;

 function solve(x,y:longint):longint;
   var
       tmp,tm,k,Lx,Rx:  longint;
   begin
     if y=0 then exit(0);
     if opt[x,y] <> -1 then exit(opt[x,y]);

     lx :=l[x,1]; rx :=l[x,2];
     if  l[x,0]=0 then exit(0);
     if  l[x,0]=1 then begin opt[x,y] :=solve(lx,y-1)+(y-1)*(m-y+1)*g[x,lx]; exit(opt[x,y]); end;
     tmp := maxlongint;
     for k :=max(0,y-son[rx]-1) to min(y-1,son[lx]) do begin
         if  k>son[lx] then continue;
         if  y-1-k > son[rx] then continue;
         tm :=solve(lx,k)+solve(rx,y-1-k)+
            k*(m-k)*g[x,lx]+(y-1-k)*(m-y+1+k)*g[x,rx];
         if tm < tmp then tmp :=tm;
         end;

     opt[x,y] :=tmp;
     exit(opt[x,y]);
   end;


 procedure Main;

   begin
     fillchar(opt,sizeof(opt),$FF);
     Ans :=solve(1,m);
     writeln(Ans/(m*(m-1)/2):0:2);
   end;

 begin
   assign(input,'hole.in'); reset(input);
   assign(output,'hole.out'); rewrite(output);
   Init;
   Main;
   close(input); close(output);
 end.