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.

Download