Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
const fi='';
      maxn=210;
var n,p,re:longint;
    a:array[1..maxn*2] of longint;
    pos,cur,sl,c,cha:array[1..maxn] of longint;
    b:array[1..maxn,0..1] of longint;
    f,tr:array[1..maxn,0..maxn] of longint;

procedure rf;
var i:longint;
begin
     read(n,p);
     for i:=1 to n do read(c[i]);
     for i:=1 to n-1 do
     begin
          read(b[i,0],b[i,1]);
          inc(sl[b[i,0]]); inc(sl[b[i,1]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+sl[i-1];
          cur[i]:=pos[i];
     end;
     for i:=1 to n-1 do
     begin
          a[cur[b[i,0]]]:=b[i,1];
          inc(cur[b[i,0]]);
          a[cur[b[i,1]]]:=b[i,0];
          inc(cur[b[i,1]]);
     end;
end;

procedure visit(x,y:longint);
var i,j,k:longint;
begin
     cha[x]:=y;
     f[x,1]:=c[x];
     for i:=pos[x] to pos[x+1]-1 do
         if a[i]<>y then
         begin
              visit(a[i],x);
              for j:=p downto 2 do
                  for k:=1 to j-1 do
                      if f[x,j]<f[x,j-k]+f[a[i],k] then
                      begin
                           f[x,j]:=f[x,j-k]+f[a[i],k];
                           tr[a[i],j]:=k;
                      end;
         end;
end;

procedure trace(x,p:longint);
var i,j,k,val:longint;
begin
     write(x,' ');
     for i:=pos[x+1]-1 downto pos[x] do
         if (a[i]<>cha[x]) and (tr[a[i],p]>0) then
         begin
              trace(a[i],tr[a[i],p]);
              p:=p-tr[a[i],p];
         end;
end;

procedure pr;
var i,j,x:longint;
begin
     for i:=1 to n do
         for j:=1 to p do
             f[i,j]:=-1000000;
     visit(1,0);
     for i:=1 to n do
         if f[i,p]>re then
         begin
              re:=f[i,p];
              x:=i;
         end;
     trace(x,p);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của RR

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.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define maxn 201
#define maxc 1000000000
long c[maxn],d[maxn][maxn],n,P,a[maxn][maxn],trace[maxn][maxn];
//FILE *p;
void visit(long u)
{
//printf("0 ");     
d[u][1]=c[u];
for(long v=1;v<=n;v++)
  if(a[u][v]==1)
    {
    a[v][u]=0;
    visit(v);
    for(long i=P;i>=1;i--)
      for(long j=1;j<=i-1;j++)
        if(d[u][i]<d[u][j]+d[v][i-j])
          {
          d[u][i]=d[u][j]+d[v][i-j];
          trace[v][i]=i-j;
          }
    }
}
void truy_vet(long u,long P)
{
//printf("1 "); 
for(long v=n;v>=1;v--)
  if(a[u][v]==1&&trace[v][P]>0)
    {
    truy_vet(v,trace[v][P]);
    P=P-trace[v][P];
    }
printf("%ld ",u);
}
void xuli()
{
long u,vt;
visit(1);
vt=1;
for(u=2;u<=n;u++)
  if(d[u][P]>d[vt][P])
    vt=u;
  truy_vet(vt,P);
}
void init()
{
for(long u=1;u<=n;u++)
  for(long k=1;k<=n;k++)
    d[u][k]=-maxc;
} 
void Enter()
{
//p=fopen("D:\\Hoc tap\\test\\PTREE\\PTREE.IN0","r");
long i,u,v;
scanf("%ld %ld",&n,&P);
for(i=1;i<=n;i++)
  scanf("%ld",&c[i]);
for(i=1;i<=n-1;i++)
  {
  scanf("%ld %ld",&u,&v);
  a[u][v]=1;
  a[v][u]=1;
  }
}         
main()
{
Enter();
init();
xuli();
//getch();
}

Code mẫu của ll931110

{$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.

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;

public class Main {
    static int n,p;
    static int[] c, father;
    static ArrayList<Integer>[] ke;
    static int[][] f,d;
    static void dfs(int i) {
        int socon = 0;
        for(int j:ke[i]) if(j!=father[i]) {
            father[j]=i;
            dfs(j);
            ++socon;
        }
        if(socon==0) {
            f[i][1] = c[i];
            f[i][0] = 0;
            return;
        }
        int s=0;
        for(int j=1;j<=p;++j) d[0][j] = -20000000;
        for(int j:ke[i]) if(j!=father[i]) {
            ++s;
            for(int t=0;t<=p;++t) {
                d[s][t]=-20000000;
                for(int k=0;k<=t;++k) d[s][t]=Math.max(d[s][t],d[s-1][k]+f[j][t-k]);
            }
        }
        for(int t=1;t<=p;++t) f[i][t] = d[socon][t-1]+c[i];
        f[i][0] = 0;
    }
    static void truyvet(int i,int p) {
        if(p==0) return;
        int socon = 0;
        ArrayList<Integer> con=new ArrayList();
        for(int j:ke[i]) if(j!=father[i]) {
            ++socon;
            con.add(j);
        }
        if(socon==0) {
            System.out.print(i+" ");
            return;
        }
        System.out.print(i+" ");
        int s=0;
        for(int j=1;j<=p;++j) d[0][j] = -20000000;
        for(int j:ke[i]) if(j!=father[i]) {
            ++s;
            for(int t=0;t<=p;++t) {
                d[s][t]=-20000000;
                for(int k=0;k<=t;++k) d[s][t]=Math.max(d[s][t],d[s-1][k]+f[j][t-k]);
            }
        }
        int x=p-1;
        Stack<Integer> ss = new Stack();
        for(int j=socon;j>=1;--j) {
            for(int k=0;k<=x;++k) if(d[j-1][k]+f[con.get(j-1)][x-k] == d[j][x]) {
                ss.push(con.get(j-1));
                ss.push(x-k);
                x = k;
                break;
            }
        }
        while(!ss.isEmpty()){
            int b=ss.pop(), a=ss.pop();
            truyvet( a, b);
        }
    }
    public static void main(String[] Args) throws Exception {
        BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(kb.readLine());
        n = Integer.parseInt(st.nextToken());
        p = Integer.parseInt(st.nextToken());
        c = new int[n+1];
        st=new StringTokenizer(kb.readLine());
        for(int i=1;i<=n;++i) c[i] = Integer.parseInt(st.nextToken());
        ke = new ArrayList[n+1];
        for(int i=1;i<=n;++i) ke[i]=new ArrayList();
        for(int i=1;i<n;++i) {
            st=new StringTokenizer(kb.readLine());
            int u=Integer.parseInt(st.nextToken()), v=Integer.parseInt(st.nextToken());
            ke[u].add(v);
            ke[v].add(u);
        }
        f=new int[n+1][p+1];
        d=new int[n+1][p+1];
        for(int i=0;i<=n;++i) for(int j=0;j<=p;++j) f[i][j]=-20000000;
        father=new int[n+1];
        dfs(1);
        int res=0, imax=0;
        for(int i=1;i<=n;++i) if(res<f[i][p]) {
            res=f[i][p];
            imax=i;
        }
        truyvet(imax,p);
    }
}