Submission #75814366

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

// https://github.com/skrewbar/cp-templates

using ll = long long;

#define all(v) (v).begin(), (v).end()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), (v).end())
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
#define by_desc(x) [](const auto& a, const auto& b) { return a.x > b.x; }

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
bool minimize(T& target, T candidate) {
    return target > candidate ? (target = candidate, true) : false;
}
template <typename T>
bool maximize(T& target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}

int w[5050], p[5050];
vector<int> childs[5050];

int mem = 0;
void findLeafs(int cur) {
    if (childs[cur].empty()) {
        mem += w[cur];
        return;
    }

    for (int child : childs[cur]) {
        if (child == p[cur])
            continue;

        findLeafs(child);
    }
}

int answer = 0;

void calc(int cur) {
    if (childs[cur].empty())
        return;

    for (int child : childs[cur]) {
        if (child == p[cur])
            continue;

        calc(child);
    }

    mem += w[cur];
    maximize(answer, mem);
    for (int child : childs[cur]) {
        if (child == p[cur])
            continue;

        mem -= w[child];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
        cin >> w[i];
    for (int i = 2; i <= N; i++) {
        cin >> p[i];
        childs[p[i]].push_back(i);
    }
    
    findLeafs(1);
    calc(1);

    if (answer > M)
        cout << "OOM";
    else
        cout << answer;

    return 0;
}

Submission Info

Judge Result