记录编号	24242	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 184] 洞窟探索	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	0.993 s
提交时间	2011-03-31 11:13:24	内存使用	17.32 MiB

type
  jp=record
    l,r,s:longint;
  end;

var
  n,m:longint;
  a,f:array[0..1500,0..1500]of longint;
  v:array[0..1500]of boolean;
  tree:Array[0..1500]of jp;

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

procedure build(i:longint);
var
  j:longint;
begin
  if tree[i].s>0 then exit;
  tree[i].s:=1;
  v[i]:=true;
  for j:=2 to n do
  if (a[i,j]>0)and(not v[j]) then
  begin
    if tree[i].l=0 then tree[i].l:=j
    else tree[i].r:=j;
    build(j);
    inc(tree[i].s,tree[j].s);
    if tree[i].r<>0 then exit;
  end;
end;

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

procedure go(i,j:longint);
var
  k,x:longint;
begin
  if (j<=1)or(tree[i].l=0) then exit;

  if f[i,j]>0 then exit;

  if tree[i].r=0 then
  begin
    go(tree[i].l,j-1);
    f[i,j]:=f[i,j]+f[tree[i].l,j-1]+a[i,tree[i].l]*(j-1)*(m-j+1);
    exit;
  end;
  f[i,j]:=maxlongint;
  for k:=0 to tree[tree[i].l].s do if (j-k-1<=tree[tree[i].r].s) then begin
  if k>j-1 then break;
    go(tree[i].l,k);
    go(tree[i].r,j-k-1);
    x:=0;
    x:=f[tree[i].l,k]+f[tree[i].r,j-k-1];
    x:=x+a[i,tree[i].l]*k*(m-k);
    x:=x+a[i,tree[i].r]*(j-k-1)*(m-j+k+1);
    if x<f[i,j] then f[i,j]:=x;
  end;
end;

procedure print;
var
  s:longint;
begin
  s:=m*(m-1) div 2;
  writeln(f[1,m]/s:0:2);
  close(input);
  close(output);
end;

begin
  init;
  build(1);
  go(1,m);
  print;
end.