我的第一道一遍AC的树形动规
type
treeee=record
lc,rc,num:longint;
end;
var
a:array[1..100,1..100]of longint;
f:array[1..100,0..100]of longint;
tree:array[1..100]of treeee;
v:array[1..100]of boolean;n,m,x,y,z,i:longint;
function dp(x,y:longint):longint;var i,max:longint;
begin
if f[x,y]<>0 then
exit(f[x,y]);
if (y=0) or (tree[x].lc=0) then
exit(0);
max:=0;
for i:=0 to y-1 do
if dp(tree[x].lc,y-i-1)+dp(tree[x].rc,i)>max then
max:=f[tree[x].lc,y-i-1]+f[tree[x].rc,i];
f[x,y]:=max+tree[x].num;
exit(f[x,y]);
end;
procedure happy(x:longint);
var i:longint;
begin
v[x]:=true;
for i:=1 to n do
if (not v[i]) and (a[i,x]<>0) then
begin
if tree[x].lc=0 then
tree[x].lc:=i
else
tree[x].rc:=i;
tree[i].num:=a[i,x];
happy(i);
end;
end;
begin
readln(n,m);
m:=m+1;
for i:=1 to n-1 do
begin
readln(x,y,z);
a[x,y]:=z;
a[y,x]:=z;
end;
fillchar(v,sizeof(v),false);
happy(1);
for i:=1 to n do
f[i,1]:=tree[i].num;
writeln(dp(1,m));
end.