悬关

提交记录，MLE+TLE

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,mark,ans,a[N],f[N],vis[N],dp[N][2];
vector<int> v[N];
int judge_circle(int x)
{
	if(vis[x])	return x;
	vis[x]=1;
	judge_circle(f[x]);
}
void dfs(int x)
{
	dp[x][1]=a[x];
	for(auto i:v[x])
	{
		if(i==mark)	continue;
		dfs(i);
		dp[x][1]+=dp[i][0];
		dp[x][0]+=max(dp[i][0],dp[i][1]);
	}
}
int solve(int x)
{
	int an;
	mark=judge_circle(x);
	dfs(mark);
	an=dp[mark][0];
	mark=f[mark];
	dfs(mark);
	return min(an,dp[mark][0]);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>f[i];
		v[f[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			ans+=solve(i);
	cout<<ans;
	return 0;
}