solution

木上のナップサック問題, @tmaehara - Qiita を読んでください。 記事とのギャップとしては「アイテムが$1$種類で費用も$1$の個数制限付きナップサック問題であって初期配列が指定されるものを$O(N)$で解きたい」部分がありますが、sliding windowを用いて$\mathrm{dp}(x) - s_i x$のように傾斜を付けた配列の最大値を取得してやれば済みます。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= int(m); -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

template <typename T, class Compare = less<T> >
class sliding_window {
    deque<pair<int, T> > data;
    Compare compare;
public:
    sliding_window(Compare const & a_compare = Compare())
        : compare(a_compare) {}
    T front() {  // O(1), minimum
        return data.front().second;
    }
    void push_back(int i, T a) {  // O(1) amortized.
        while (not data.empty() and compare(a, data.back().second)) {
            data.pop_back();
        }
        data.emplace_back(i, a);
    }
    void pop_front(int i) {
        if (data.front().first == i) {
            data.pop_front();
        }
    }
};

constexpr ll INF = (ll) 1e18 + 9;
int main() {
    while (true) {
        // input
        int n, k; cin >> n >> k;
        if (n == 0 and k == 0) break;
        vector<int> h(n);
        vector<int> s(n);
        REP (i, n) cin >> h[i];
        REP (i, n) cin >> s[i];
        vector<int> parent(n);
        parent[0] = -1;
        REP3 (i, 1, n) {
            cin >> parent[i];
            -- parent[i];
        }
        vector<int> l(n);
        l[0] = -1;
        REP3 (i, 1, n) cin >> l[i];

        // solve
        vector<vector<int> > children(n);
        REP3 (i, 1, n) {
            children[parent[i]].push_back(i);
        }
        REP (i, n) {
            sort(ALL(children[i]), [&](int i, int j) { return l[i] < l[j]; });
        }

        function<void (int, vector<ll> &)> go = [&](int i, vector<ll> & dp0) {
            vector<ll> dp1 = dp0;
            int h_prev = 0;

            REP (edge, children[i].size() + 1) {
                int j = (edge < children[i].size() ? children[i][edge] : -1);
                int cnt = min(k, j == -1 ? h[i] : l[j]) - h_prev;

                // update
                sliding_window<ll, greater<ll> > window;
                REP (x, k + 1) {
                    window.push_back(x, dp1[x] - (ll) s[i] * x);
                    chmax(dp0[x], window.front() + (ll) s[i] * x);
                    if (x - cnt >= 0) {
                        window.pop_front(x - cnt);
                    }
                }
                if (j == -1) break;

                // shift
                REP3R (x, cnt, k + 1) {
                    dp1[x] = dp1[x - cnt] + (ll) s[i] * cnt;
                }
                REP (x, cnt) {
                    dp1[x] = - INF;
                }
                h_prev += cnt;
                if (h_prev < l[j]) break;

                // recur
                go(j, dp1);
            }

            REP (x, k) {
                chmax(dp0[x + 1], dp0[x]);
            }
            return dp0;
        };

        constexpr int root = 0;
        vector<ll> dp(k + 1, - INF);
        dp[0] = 0;
        go(root, dp);

        // output
        cout << dp[k] << endl;
    }
    return 0;
}