记录编号	605707	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	4173.[USACO25 Feb Gold]Bessie s Function	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	3.623 s
提交时间	2025-09-06 16:20:45	内存使用	20.25 MiB

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 214514;

int n;
int a[N];
int c[N];
vector<int> tree[N];
bool vis[N];
int id[N];
long long dp[N][2];
long long f[N][2][2];
bool rvis[N];
vector<int> ring;
long long res;

void dfs (int now) {
	dp[now][1] = c[now];
	for (auto son : tree[now]) {
		if (rvis[son]) {
			continue;
		}
		dfs (son);
		dp[now][0] += dp[son][1];
		dp[now][1] += min (dp[son][0], dp[son][1]);
	}
}

int main () {
	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		tree[a[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}

	for (int i = 1; i <= n; i++) {
		if (vis[i]) {
			continue;
		}
		int ti = i;
		while (!vis[ti]) {
			vis[ti] = true;
			id[ti] = i;
			ti = a[ti];
		}
		if (id[ti] < i) {
			continue;
		}

		ring.clear();
		while (!rvis[ti]) {
			rvis[ti] = true;
			ring.push_back(ti);
			ti = a[ti];
		}
		int l = 0;
		int r = *ring.rbegin();
		if (ring.size() == 1) {
			dfs (r);
			res += dp[r][1] - c[r];
			continue;
		}

		bool flag = false;
		for (auto ri : ring) {
			dfs (ri);
			if (flag) {
				f[ri][0][0] = f[l][1][0] + dp[ri][0];
				f[ri][0][1] = f[l][1][1] + dp[ri][0];
				f[ri][1][0] = min (f[l][0][0], f[l][1][0]) + dp[ri][1];
				f[ri][1][1] = min (f[l][0][1], f[l][1][1]) + dp[ri][1];
			}
			else {
				f[ri][0][0] = dp[ri][0];
				f[ri][0][1] = 1e18;
				f[ri][1][1] = dp[ri][1];
				f[ri][1][0] = 1e18;
				flag = true;
			}
			l = ri;
		}
		res += min (f[r][0][1], min (f[r][1][1], f[r][1][0]));
	}

	cout << res << endl;
	
	return 0;
}