刚学OI，新人求助QAQ，Island那题，luogu AC，BZOJ RE

//1791: [Ioi2008]Island 岛屿
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int MaxN=1000000,MaxM=1000000;
int n;
int head[MaxN+1],to[MaxM*2+1],w[MaxM*2+1],next[MaxM*2+1],tot=1;
void add(int x,int y,int z)
{
	to[tot]=y,w[tot]=z,next[tot]=head[x],head[x]=tot++;
	return;
}
template<typename integer>inline const void Read(integer &ans)
{
	ans=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
		ans=ans*10+c-48,c=getchar();
	return;
}
template<typename integer>inline const integer Max(const integer &a,const integer &b)
{
	return a>b?a:b;
}
bool v[MaxN+1],v2[MaxN+1],isoc[MaxN+1];
int dot[MaxN+1],edg[MaxN+1],cnt,st;
ll D[MaxN+1],F[MaxN+1];
inline const bool DFS(int x,int f,int e)
{
	if(v[x])
		return edg[cnt]=w[e],st=x,1;
	if(v2[x])
		return 0;
	v[x]=v2[x]=1;
	bool p=0;
	for(int i=head[x];i;i=next[i])
		if(i!=((e-1)^1)+1)
			p=DFS(to[i],x,i)||p;
	if(p)
		dot[cnt++]=x,isoc[x]=1;
	if(st==x)
		p=0;
	if(p)
		edg[cnt]=w[e];
	v[x]=0;
	return p;
}
inline const ll DP(int x,int f)
{
	ll s=0;
	D[x]=F[x]=0;
	for(int i=head[x];i;i=next[i])
		if(to[i]!=f&&!isoc[to[i]])
			s=Max(DP(to[i],x),s),F[x]=Max(F[x],D[x]+D[to[i]]+w[i]),D[x]=Max(D[x],D[to[i]]+w[i]);
	return Max(F[x],s);
}
ll s[MaxN*2+1]={0},dp[MaxN+2+1]={0};
inline const ll Part(int root)
{
	ll BF=0;
	cnt=0;
	DFS(root,0,0);
	for(int i=1;i<cnt*2;i++)
		s[i]=s[i-1]+edg[i%cnt];
	deque<int>q;
	for(int i=0;i<cnt;i++)
		BF=Max(DP(dot[i],0),BF),dp[i]=dp[cnt+i]=D[dot[i]];
	for(int i=0;i<cnt*2;i++)
	{
		while(q.size()&&(i-q.front()>=cnt))
			q.pop_front();
		if(q.size())
			BF=Max(BF,dp[q.front()]+s[i]-s[q.front()]+dp[i]);
		while(q.size()&&(dp[q.back()]-s[q.back()]<=dp[i]-s[i]))
			q.pop_back();
		q.push_back(i);
	}
	return BF;
}
int main()
{
	int a,b;
	ll ans=0;
	Read(n);
	for(int i=0;i<n;i++)
		Read(a),Read(b),add(i+1,a,b),add(a,i+1,b);
	for(int i=1;i<=n;i++)
		if(!v2[i])
			ans+=Part(i);
	printf("%lld\n",ans);
	return 0;
}