讨论 / treedp 求改错
zhmoonlight 2012-10-07 23:15:00
点我顶贴 收藏 删除
type atype=record

left,right:integer;

end;

btype=record

cs,data:integer;

c:array[0..1000] of integer;

end;

var a:array[0..1000] of btype;

b:array[0..1000] of atype;

v:array[0..1000,0..100] of longint;

i,x,y,n,m:integer;

procedure tree(i:integer);

var j:integer;

begin

if a[i].cs=0 then exit;

b[i].left:=a[i].c[1];

for j:=1 to a[i].cs-1 do

b[a[i].c[j]].right:=a[i].c[j+1];

for j:=1 to a[i].cs do

tree(a[i].c[j]);

end;

function dp(i,m:integer):longint;

var s,j:integer;

begin

if m=0 then exit(0);

if v[i,m]<>0 then exit(v[i,m]);

for j:=0 to m-1 do begin

s:=dp(b[i].left,j)+dp(b[i].right,m-j-1)+a[i].data;

if s>v[i,m] then v[i,m]:=s;

end;

dp:=v[i,m];

end;

begin

readln(n,m);

for i:=1 to n do

read(a[i].data);

readln;

for i:=1 to n do begin

readln(x,y);

inc(a[x].cs);

a[x].c[a[x].cs]:=y;

end;

tree(0);

writeln(dp(0,m+1));

end.

查看更多回复
提交回复