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

{
 haoi2009  moni1 t2 hole
 dfs rp++ tree DP
 time:2009.4.21
}
program cch(input,output);
const
 maxf=1000000000;
var
 f:array[0..2000,0..1000] of longint;
 root,n,m,ans:longint;
 rchild,lchild,sum:array[0..2000] of integer;
 map:array[0..2000,0..2000] of longint;
 flag:array[0..2000] of boolean;

procedure init;
var
 i,j,x,y,l:longint;
begin
 assign(input,'hole.in');
 assign(output,'hole.out');
 reset(input);
 rewrite(output);
 readln(n,m);
 for i:=1 to n do
  for j:=1 to n do
   map[i,j]:=0;
 for i:=1 to n-1 do
  begin
   readln(x,y,l);
   map[x,y]:=l; map[y,x]:=l;
  end;
 for i:=0 to n do
  for j:=0 to m do
   f[i,j]:=-1;
 for i:=1 to n do
  f[i,1]:=0;
 for i:=1 to m do f[0,i]:=maxf;
end;

function small(x,y:longint):longint;
begin
 if x<y then exit(x)
  else exit(y);
end;

function dfs(k,p:longint):longint;
var
 i,min:longint;
begin
 if f[k,p]<>-1 then exit(f[k,p]);
 min:=maxf;
 for i:=1 to p-2 do
  begin
   if i>sum[lchild[k]] then break;
   if p-1-i>sum[rchild[k]] then continue;
   min:=small(min,dfs(lchild[k],i)+dfs(rchild[k],p-1-i)+map[k,lchild[k]]*i*(m-i)+map[k,rchild[k]]*(p-1-i)*(m-p+1+i));
  end;
 min:=small(min,dfs(lchild[k],p-1)+map[k,lchild[k]]*(p-1)*(m-p+1));
 min:=small(min,dfs(rchild[k],p-1)+map[k,rchild[k]]*(p-1)*(m-p+1));
 f[k,p]:=min;
 exit(min);
end;

procedure maketree(k:longint);
var
 i:longint;
begin
 if sum[k]<>0 then exit;
 flag[k]:=false;
 lchild[k]:=0; rchild[k]:=0;
 sum[k]:=1;
 for i:=1 to n do
  if (map[k,i]>0)and(flag[i]) then
   begin
    if lchild[k]=0 then lchild[k]:=i
                   else rchild[k]:=i;
    maketree(i);
    inc(sum[k],sum[i]);
   end;
end;

procedure main;
var
 i:longint;
begin
 root:=1;
 for i:=1 to n do flag[i]:=true;
 sum[0]:=0;
 maketree(root);
 ans:=dfs(root,m);
end;

procedure print;
var
 ans1:real;
begin
 m:=(m-1)*m div 2;
 ans1:=ans/m;
 writeln(ans1:0:2);
 close(input);
 close(output);
end;

begin
 init;
 main;
 print;
end.