求查是写法问题还是常数问题。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pob pop_back
#define pof pop_front
using namespace std;

typedef pair<int,ll> pil;

const int maxn=1000010;

bool on_ring[maxn];// judge the point on the ring or not
bool vis[maxn];
struct side{
	int to;ll len;int ch;//characterstic code
};int cht=0;
vector<side>edge[maxn];
ll lr[maxn],zj[maxn];//the longest route und zhijing(d)

vector<pil>jhs[maxn];//note the point on one ring and its len to next point into this array
ll lent[maxn];//the sum of the len on the ring
int tot=0;//number of jhs

int n;

//tarjan-like algo
pil sta[maxn];int head=0;
bool ins[maxn];//in the stack

void tarjan(int nowa,int fa,int chf){
	vis[nowa]=1;
	for(side tmp:edge[nowa]){
		int go=tmp.to;ll len=tmp.len;int ch=tmp.ch;
		if(ins[go]&&ch!=chf){
			tot++;
			jhs[tot].pb(mp(nowa,len));
			lent[tot]+=len;
			on_ring[nowa]=1;
			for(int i=head;i;i--){
				jhs[tot].pb(sta[i]);
				lent[tot]+=sta[i].second;
				on_ring[sta[i].first]=1;
				if(sta[i].first==go)break;
			}
			continue;
		}
		if(go==fa||vis[go])continue;
		sta[++head]=mp(nowa,len);
		ins[nowa]=1;
		tarjan(go,nowa,ch);
		head--;
		ins[nowa]=0;
	}
}

/////

//DP on the tree

void dfs(int nowa,int fa){
	ll m1,m2;m1=m2=0xcfcfcfcfcfcfcfcf;
	for(side tmp:edge[nowa]){
		int go=tmp.to;ll len=tmp.len;
		if(go==fa||on_ring[go])continue;
		dfs(go,nowa);
		ll lt=lr[go]+len;
		if(m2<lt)swap(m2,lt);
		if(m1<m2)swap(m1,m2);
		zj[nowa]=max(zj[nowa],zj[go]);
	}
	lr[nowa]=max(m1,lr[nowa]);
	zj[nowa]=max(zj[nowa],max(m1,0ll)+max(m2,0ll));
}

/////

//get zj (transport on the ring)

ll dist[2*maxn];
deque<int>dq;

ll solve(int tree){//in which jhs
	ll res=0;
	int siz=jhs[tree].size();
	dq.clear();
	for(int i=0;i<siz;i++){
		res=max(res,zj[jhs[tree][i].first]);
		dist[i]=dist[i+siz]=jhs[tree][i].second;
	}
	for(int i=1;i<siz*2;i++)dist[i]+=dist[i-1];
	
	dq.pb(0);
	
	for(int i=1;i<2*siz;i++){
		while(dq.size()&&i-dq.front()>=siz)
		dq.pof();
		res=max(res,lr[jhs[tree][i%siz].first]+lr[jhs[tree][dq.front()%siz].first]+dist[i]-dist[dq.front()]);
		while(dq.size()&&lr[jhs[tree][dq.back()%siz].first]-dist[dq.back()]<=lr[jhs[tree][i%siz].first]-dist[i])
		dq.pob();
		dq.pb(i);
	}
	return res;
}

/////

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n;
	
	int ver;ll len;
	for(int i=1;i<=n;i++){
		cin>>ver>>len;
		edge[i].pb((side){ver,len,++cht});
		edge[ver].pb((side){i,len,cht});
	}
	
	for(int i=1;i<=n;i++){
		if(!vis[i])tarjan(i,0,0);
	}
	
	for(int i=1;i<=tot;i++){
		for(pil tmp:jhs[i])dfs(tmp.first,0);
	}
	
	ll ans=0;
	
	for(int i=1;i<=tot;i++){
		ans+=solve(i);
	}
	
	cout<<ans<<endl;
	
	return 0;	
}