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=100;
      maxm=2000;
var n,m,re:longint;
    c,v:array[1..maxn] of longint;
    a:array[1..maxn,1..maxn] of boolean;
    f:array[1..maxn,0..maxm] of longint;

procedure rf;
var i,x,y:longint;
begin
     read(n,m);
     for i:=2 to n do read(v[i]);
     for i:=2 to n do read(c[i]);
     for i:=1 to n-1 do
     begin
          read(x,y);
          a[x,y]:=true;
          a[y,x]:=true;
     end;
end;

procedure visit(x,cc,vv:longint);
var i,j:longint;
begin
     if cc>m then exit;
     for i:=1 to n do
          if a[x,i] then
          begin
               a[i,x]:=false;
               for j:=cc+c[i] to m do
                    f[i,j]:=f[x,j-c[i]]+v[i];
               visit(i,cc+c[i],vv+v[i]);
               for j:=cc+c[i] to m do f[x,j]:=max(f[x,j],f[i,j]);
          end;
end;

procedure pr;
var j:longint;
begin
     visit(1,0,0);
     for j:=0 to m do re:=max(re,f[1,j]);
     writeln(re);
end;

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

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 110;
const int M = 2020;
using namespace std;

int n, m, l, r;
vector<int> a[N], child[N];
int Q[N], V[N], C[N], now[N]; bool was[N];
int* G[N][M];

void BFS() {
    l = 1, r = 1; int i, u, v;
    Q[1] = 1; was[1] = true;
    while (l <= r) {
        u = Q[l++];
        for(int i = 0; i < a[u].size(); i++) {
            v = a[u][i];
            if (!was[v]) {
                was[v] = true;
                child[u].push_back(v);
                Q[++r] = v;
            }
        }
    }
}

int DP(int u, int k) {
    if (now[u] >= k) return V[u] + G[u][k][child[u].size()];
    int i, v;
    for(int money = now[u] + 1; money <= k; money++) {
        G[u][money] = new int[child[u].size() + 1]; G[u][money][0] = 0;
        for(i = 1; i <= child[u].size(); i++) {
            v = child[u][i - 1];
            G[u][money][i] = G[u][money][i - 1];
            for(int pay = money; pay >= C[v]; pay--)
                G[u][money][i] = max(G[u][money][i], G[u][money - pay][i - 1] + DP(v, pay - C[v]));
        }
    }
    now[u] = k;
    return V[u] + G[u][k][child[u].size()];
}

int main()
{
    scanf("%d %d", &n, &m);
    int i, j, u, v, sv = 0, sc = 0;
    for(i = 2; i <= n; i++) {scanf("%d", &V[i]); sv += V[i];}
    for(i = 2; i <= n; i++) {scanf("%d", &C[i]); sc += C[i];}
    if (m >= sc) {printf("%d", sv); return 0;}
    for(i = 1; i < n; i++) {
        scanf("%d %d", &u, &v);
        a[u].push_back(v); a[v].push_back(u);
    }
    BFS();
    memset(now, 255, sizeof now);
    for(i = 1; i <= n; i++) {
        G[i][0] = new int[child[i].size()];
        memset(G[i][0], 0, sizeof G[i][0]);
    }
    printf("%d", DP(1, m));
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define MAXN 111 
#define PB push_back
using namespace std;

int debug=0;
int n,m,value[MAXN],c[MAXN],f[MAXN][2011],g[MAXN][2011],visited[MAXN],sumc[MAXN];
vector<int> ke[MAXN];

void inp() {
    scanf("%d %d",&n,&m);
    FOR(i,2,n) scanf("%d",&value[i]);
    FOR(i,2,n) scanf("%d",&c[i]);
    FOR(i,2,n) {
        int u,v; scanf("%d %d",&u,&v);
        ke[u].PB(v);
        ke[v].PB(u);
    }
}

void dfs1(int u) {
    sumc[u]=c[u];
    FORV(v,ke[u]) {
        if (sumc[*v]>=0) continue;
        dfs1(*v);
        sumc[u]+=sumc[*v];
    }
    if (sumc[u]>m) sumc[u]=m;
}

void dfs2(int u) {
    visited[u]=1;
    f[u][0]=0;
    f[u][c[u]]=value[u];
    g[u][0]=0;
    int now=0;
    FORV(v,ke[u]) {
        now++;
        if (visited[*v]) continue;
        dfs2(*v);

        FORD(p,sumc[u],0)
        FOR(tov,0,sumc[*v])
            if (tov<=p) g[u][p] >?= f[*v][tov]+g[u][p-tov];
    }

    FOR(p,c[u],sumc[u])
    if (g[u][p-c[u]])
        f[u][p] >?= value[u]+g[u][p-c[u]];
}

void solve() {
    memset(sumc,-1,sizeof sumc);
    dfs1(1);
    if (debug) {
        FOR(i,1,n) cout<<sumc[i]<<" ";
        cout<<endl;
    }
    FOR(i,1,n)
    FOR(j,0,m)
        g[i][j]=f[i][j]=-1000111000;
    dfs2(1);

    if (debug) {
        FOR(i,1,n) {
            cout<<i<<": ";
            FOR(j,0,m)
            if (f[i][j]>=0) cout<<"("<<j<<","<<f[i][j]<<") ";
            cout<<endl;
        }
    }

    int res=0;
    FOR(i,0,m) res >?= f[1][i];
    cout<<res;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}