PTREE - Cây P đỉnh ( Cơ bản )
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program PTREE;
const
input = '';
output = '';
maxn = 200;
maxv = 100000000;
var
free: array[1..maxn] of boolean;
c: array[1..maxn,1..maxn] of boolean;
F,child: array[1..maxn,0..maxn] of integer;
p,trace: array[1..maxn,1..maxn,0..maxn] of integer;
n,k: integer;
a,list,nchi: array[1..maxn] of integer;
nlist: integer;
procedure init;
var
fi: text;
i,x,y,j,t: integer;
begin
assign(fi, input);
reset(fi);
readln(fi, n, k);
fillchar(c, sizeof(c), false);
for i := 1 to n do read(fi, a[i]);
for i := 1 to n - 1 do
begin
readln(fi, x, y);
c[x,y] := true;
c[y,x] := true;
end;
close(fi);
for i := 1 to n do
for j := 1 to n do
for t := 1 to n do p[i,j,t] := -maxv;
for i := 1 to n do
for j := 1 to n do p[i,j,0] := 0;
for i := 1 to n do
for j := 1 to n do F[i,j] := -maxv;
for i := 1 to n do F[i,0] := 0;
fillchar(free, sizeof(free), true);
end;
procedure DFS(u: integer);
var
v: integer;
begin
free[u] := false;
nchi[u] := 0;
for v := 1 to n do
if free[v] and c[u,v] then
begin
inc(nchi[u]);
child[u,nchi[u]] := v;
DFS(v);
end;
end;
procedure dp(u: integer);
var
i,j,t: integer;
begin
if nchi[u] = 0 then
begin
F[u,1] := a[u];
exit;
end;
for i := 1 to nchi[u] do dp(child[u,i]);
for i := 0 to n do
begin
p[u,1,i] := F[child[u,1],i];
trace[u,1,i] := i;
end;
for i := 2 to nchi[u] do
for j := 0 to n do
for t := 0 to j do
if p[u,i,j] < p[u,i - 1,t] + F[child[u,i],j - t] then
begin
p[u,i,j] := p[u,i - 1,t] + F[child[u,i],j - t];
trace[u,i,j] := j - t;
end;
for i := 1 to n - 1 do F[u,i] := p[u,nchi[u],i - 1] + a[u];
end;
procedure add(x: integer);
begin
inc(nlist);
list[nlist] := x;
end;
procedure track(u,val: integer);
var
j,t: integer;
begin
if val <= 1 then
begin
if val = 1 then add(u);
exit;
end;
for j := nchi[u] downto 1 do
begin
t := trace[u,j,val - 1];
val := val - t;
track(child[u,j],t);
end;
add(u);
end;
procedure printresult;
var
fo: text;
i,j,t,u,max: integer;
begin
assign(fo, output);
rewrite(fo);
max := -maxv;
u := 0;
for i := 1 to n do if max < F[i,k] then
begin
max := F[i,k];
u := i;
end;
nlist := 0;
track(u,k);
for i := 1 to k - 1 do
for j := i + 1 to k do
if list[i] > list[j] then
begin
t := list[i];
list[i] := list[j];
list[j] := t;
end;
for i := 1 to k do write(fo, list[i], ' ');
close(fo);
end;
begin
init;
DFS(1);
dp(1);
printresult;
end.