来自"NOCOW"

f[i,j]表示以i为根的子树保留j条树枝可以得到得最多的苹果树

program djy;
var
  a:array[1..100,1..100] of longint;
  f:array[1..100,0..100] of longint;
  flag:array[1..100,1..100] of boolean;
  visited:array[1..100] of boolean;
  n,m:longint;
procedure init;
var
  i,x,y,z:longint;
begin
  readln(n,m);
  for i:=1 to n-1 do
  begin
    readln(x,y,z);
    a[x,y]:=z;
    flag[x,y]:=true;
    a[y,x]:=z;
    flag[y,x]:=true;
  end;
end;
procedure search(i:longint);
var
  j,k,left,right:longint;
begin
  visited[i]:=true;
  left:=0;
  right:=0;
  for j:=1 to n do
  if (flag[i,j]=true) and (visited[j]=false) then
  begin
    if left=0 then left:=j
    else right:=j;
    search(j);
  end;
  if not((left=0) and (right=0)) then
  begin
    for j:=0 to m do
    for k:=0 to m do
    if (j+k+2<=m) and (f[left,j]+f[right,k]+a[i,left]+a[i,right]>f[i,j+k+2]) then f[i,j+k+2]:=f[left,j]+f[right,k]+a[i,left]+a[i,right];{左右子树都选}
    for j:=0 to m do
    if (j+1<=m) and (f[left,j]+a[i,left]>f[i,j+1]) then f[i,j+1]:=f[left,j]+a[i,left];{只选左子树}
    for k:=0 to m do
    if (k+1<=m) and (f[right,k]+a[i,right]>f[i,k+1]) then f[i,k+1]:=f[right,k]+a[i,right];{只选右子树}
  end;
end;
procedure print;
begin
  writeln(f[1,m]);
end;
begin
  init;
  search(1);
  print;
end.

这道题,可以马上看出是树形Dp,f[i,j]表示以i为根的子树(还包括 [i与 i的父亲] 这条边)内,保存j条边最多可以有多少苹果,显然f[i,j]=max(f[left[i],k]+f[right[i],j-k-1])+apple[i]; 记忆化搜索实现.

program cao;
const
  maxn=110;
 
var
  left,right,value:array[0..maxn] of longint;
  map:array[0..maxn,0..maxn] of longint;
  flag:array[0..maxn] of boolean;
  f:array[0..maxn,0..maxn] of longint;
  a,b,c,i,j,k,p,q,tmp,n:longint;
 
procedure swap(var a,b:longint);
begin
  tmp:=a;
  a:=b;
  b:=tmp;
end;
 
function dfs(v,rest:longint):longint;
var
  i,j,k:longint;
begin
  if (v=0)and(rest<>0) then exit(-maxint);
  if (v=0)or(rest=0) then exit(0);
  if f[v,rest]<>0 then exit(f[v,rest]);
  k:=0;
  for i:=0 to rest-1 do
  begin
    j:=dfs(left[v],i)+dfs(right[v],rest-i-1);
    if j>k then k:=j;
  end;
  f[v,rest]:=k+value[v];
  dfs:=f[v,rest];
end;
 
procedure workout_tree(v:longint);
var
  i:longint;
begin
  flag[v]:=true;
  for i:=1 to n do
    if (flag[i]=false)and(map[v,i]>0) then
    begin
      left[v]:=i;
      value[i]:=map[v,i];
      workout_tree(i);
      break;
    end;
  for i:=i+1 to n do
    if (flag[i]=false)and(map[v,i]>0) then
    begin
      right[v]:=i;
      value[i]:=map[v,i];
      workout_tree(i);
      break;
    end;
end;
 
begin
  read(n,q);
  for i:=1 to n-1 do
  begin
    read(a,b,map[a,b]);
    map[b,a]:=map[a,b];
  end;
  workout_tree(1);
  writeln(dfs(1,q+1));
end.