二叉苹果树树形DP

题意/Description：

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
2 5
/
3 4
/
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。

读入/Input：

第1行2个数，N和Q。 N表示在树枚举的点数。Q表示应保留的分支数量。

下来N - 1行中包含分支的描述。每个描述包括三个整数用空格分开的。它们的前两个由它的结束点定义分支。第三个数字上定义这个分支苹果的数量。你可以假设没有分支包含超过30000苹果。

输出/Output：

一个数，最多能留住的苹果的数量。

题解/solution：

这个题目都讲到了二叉了，很容易的想到树型DP。不讲废话，进入话题。

如果只有一个容量，取左右两边最大值。

f[t,x]:=max(g[t,l[t]],g[t,r[t]]);

如果大于一个容量，先设左右两边都被分配。

f[t,x]:=max(f[t,x],f[l[t],i]+f[r[t],x-2-i]);

然后只取左边或只取右边。

f[t,x]:=max(f[t,x],f[l[t],x-1]+g[t,l[t]]); 或 f[t,x]:=max(f[t,x],f[r[t],x-1]+g[t,r[t]]);

代码/Code：

var
  n,q,o:longint;
  a,g,f:array [0..101,0..101] of longint;
  v:array [0..101] of boolean;
  l,r,du:array [0..101] of longint;
function max(t,k:longint):longint;
begin
  if t>k then exit(t);
  exit(k);
end;

procedure tree(x:longint);
var
  i:longint;
begin
  if x=0 then exit;
  v[x]:=true;
  for i:=1 to a[x,0] do
    if not v[a[x,i]] then
      if l[x]=0 then l[x]:=a[x,i]
                else r[x]:=a[x,i];
  tree(l[x]);
  tree(r[x]);
end;

procedure main(t,x:longint);
var
  i:longint;
begin
  if (x=0) or (t=0) then
    begin
      f[t,x]:=0;
      exit;
    end;
  if f[t,x]>0 then exit;
  if x=1 then
    begin
      f[t,x]:=max(g[t,l[t]],g[t,r[t]]);
      exit;
    end;
  for i:=0 to x-2 do
    begin
      main(l[t],i);
      main(r[t],x-2-i);
      f[t,x]:=max(f[t,x],f[l[t],i]+f[r[t],x-2-i]);
    end;
  f[t,x]:=f[t,x]+g[t,l[t]]+g[t,r[t]];
  main(l[t],x-1);
  f[t,x]:=max(f[t,x],f[l[t],x-1]+g[t,l[t]]);
  main(r[t],x-1);
  f[t,x]:=max(f[t,x],f[r[t],x-1]+g[t,r[t]]);
end;

procedure init;
var
  i,x,y,z:longint;
begin
  readln(n,q);
  for i:=1 to n-1 do
    begin
      readln(x,y,z);
      g[x,y]:=z; g[y,x]:=z;
      inc(a[x,0]); a[x,a[x,0]]:=y;
      inc(a[y,0]); a[y,a[y,0]]:=x;
    end;
  o:=1;
  for i:=1 to n do
    if a[i,0]=2 then
      begin
        o:=i;
        break;
      end;
end;

begin
  init;
  tree(o);
  main(o,q);
  write(f[o,q]);
end.

二叉苹果树 树形DP

二叉苹果树树形DP