Submission #2115874

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[22], a[22], p[22], n, res[1 << 19]; vector<int>x[22];

void dfs(int pos) {
	for (int i = 0; i < x[pos].size(); i++) dfs(x[pos][i]);
	for (int i = 0; i < (1 << x[pos].size()); i++) res[i] = (1 << 30);
	res[0] = 0;
	for (int i = 0; i < (1 << x[pos].size()); i++) {
		int sum = 0; for (int j = 0; j < x[pos].size(); j++) { if ((i&(1 << j)) != 0) sum += a[x[pos][j]]; }
		for (int j = 0; j < x[pos].size(); j++) {
			if ((i&(1 << j)) != 0) continue;
			res[i + (1 << j)] = min(res[i + (1 << j)], max(res[i], sum + dp[x[pos][j]]));
		}
	}
	dp[pos] = res[(1 << x[pos].size()) - 1];
	int R = a[pos];
	for (int i = 0; i < x[pos].size(); i++) R += a[x[pos][i]];
	dp[pos] = max(dp[pos], R);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 2; i <= n; i++) { cin >> p[i]; x[p[i]].push_back(i); }
	dfs(1);
	cout << dp[1] << endl;
	return 0;
}

Submission Info

Judge Result