PTREE - Cây P đỉnh ( Cơ bản )
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
const
oo = 1000111000;
var
n,p,i,u,v : longint;
deg,c,father : array[1..222] of longint;
ke,f,trace : array[1..222,0..222] of longint;
procedure visit(u:longint);
var
v,i,a,b,tmp:longint;
begin
f[u,0]:=0; f[u,1]:=c[u];
for i:=1 to deg[u] do
begin
v:=ke[u,i];
if f[v,0]=0 then continue;
father[v]:=u;
visit(v);
for a:=p downto 1 do
for b:=1 to a-1 do
begin
tmp:=f[v,b]+f[u,a-b];
if tmp>f[u,a] then
begin
f[u,a]:=tmp;
trace[v,a]:=b;
end;
end;
end;
end;
procedure print(u,k:longint);
var
v,i:longint;
begin
write(u,' ');
for i:=deg[u] downto 1 do
begin
v:=ke[u,i];
if v=father[u] then continue;
if trace[v,k]>0 then
print(v,trace[v,k]);
dec(k,trace[v,k]);
end;
end;
procedure ans;
var
i,res:longint;
begin
res:=1;
for i:=1 to n do
if f[i,p]>f[res,p] then res:=i;
print(res,p);
end;
begin
read(n,p);
for u:=1 to n do
for i:=0 to p do
f[u,i]:=-oo;
for i:=1 to n do read(c[i]);
for i:=1 to n-1 do
begin
read(u,v);
inc(deg[u]); inc(deg[v]);
ke[u,deg[u]]:=v;
ke[v,deg[v]]:=u;
end;
visit(1);
ans;
end.