Submission #75814672

---

Source Code Expand

#include <iostream>
#include<set>
#include<vector>

using namespace std;

int N, M, w[5001];
vector<int>p[5001];
bool vis[5001];

bool Es(set<int> &S,int n) {
	for (int i:p[n])
		if (S.find(i) == S.end())
			return false;
	return true;
}

int main() {
	int v;
	cin >> N >> M;
	for (int i = 1; N >= i; ++i)
		cin >> w[i];
	for (int i = 2; N >= i; ++i) {
		cin >> v;
		vis[v] = true;
		p[v].push_back(i);
	}
	set<int> S;
	int m = 0;
	for (int i = 1; N >= i; ++i) {
		if (!vis[i]) {
			S.insert(i);
			m += w[i];
		}
	}
	int Mm = m;
	for (int i = 1; N >= i; ++i) {
		if (vis[i] and Es(S, i)) {
			S.insert(i);
			m += w[i];
			if (m > M)
				break;
			if (Mm < m)
				Mm = m;
			for (int j:p[i]){
				S.erase(j);
				m-=w[j];
			}
			vis[i] = false;
			i = 1;
		}
	}
	if (M < m)
		cout << "OOM";
	else
		cout << Mm;
}

Submission Info

Judge Result