比赛 果蝇王邀请赛div2 评测结果 AATTTTTAAAAAATTTTTTT
题目名称 蜜雪冰城甜蜜蜜 最终得分 40
用户昵称 赵飞羽 运行时间 37.833 s
代码语言 C++ 内存使用 3.51 MiB
提交时间 2026-08-27 10:29:39
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int N = 710;
int n, fa[N], a[110], b[110], c[N], flg1 = 1, flg2 = 1, ans = 9e18;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("sweet.in", "r", stdin);
	freopen("sweet.out", "w", stdout);
	cin >> n;
	for (int i = 2; i <= n; i++) {
		cin >> fa[i];
		if (fa[i] != 1) flg1 = 0;
		if (fa[i] != i - 1) flg2 = 0;
	}
	for (int i = 1; i <= n; i++) cin >> c[i];
	if (flg2) for (int i = 1; i <= n; i++) ans = min(ans, c[i] * (n - i + 1));
	else if (flg1) for (int i = 1; i <= n; i++) ans = min(ans, 2LL * c[i]);
	else {
		srand(time(0)<<7);
		int m, cnt, flg, x, idx;
		for (int k = 1; k <= 1000000; k++) {
			for (int i = 1; i <= n; i++) a[i] = b[i] = 0;
			m = rand() % n + 1;
			cnt = 0;
			for (int i = 1; i <= m; i++) {
				a[i] = rand() % n + 1;
				cnt += c[a[i]];
				x = a[i];
				while (x) {
					b[x]++;
					x = fa[x];
				}
			}
			for (int i = 1; i <= n; i++) {
				x = i;
				flg = 1;
				idx = 1;
				while (x) {
					if (b[x] >= idx) {
						flg = 0;
						break;
					}
					idx++;
					x = fa[x];
				}
				if (flg) break;
			}
			if (!flg) ans = min(ans, cnt);
		}
	}
	cout << ans;
	return 0;
}