求义父

#include <bits/stdc++.h>
#define int long long
const int N= 1e6+ 10, M= 2e5+ 10, inf= 1e9+ 10;
inline int read() {
    int x= 0, f= 1;
    char ch= getchar();
    for (; ! isdigit(ch); ch= getchar()) if (ch== '-') f= -1;
    for (; isdigit(ch); ch= getchar()) x= (x<< 3)+ (x<< 1)+ (ch^ 48);
    return x*= f;
}
using namespace std;
int n, tot, cnt, len=1;
struct edge { int to, nxt, w; } E[N* 2];
map< pair< int, int>, int> mp;
vector< int> circle[N];
stack< int> s;
int dfn[N], low[N], vis[N], scc[N], siz[N], head[N], vb[N], fr[N];
void add( int u, int v, int z) { E[++len]= {v, head[u], z}, head[u]= len; }
void tarjan( int u) {
    dfn[u]= low[u]= ++tot, s.push(u), vis[u]= 1;
    for ( int i= head[u], v; i; i= E[i].nxt) {
        if (vb[i]&& vb[i^ 1]) continue ; ; vb[i]= vb[i^ 1]= 1;
        if (! dfn[(v= E[i].to)]) tarjan(v), low[u]= min(low[u], low[v]);
        else if (vis[v]) low[u]= min(low[u], dfn[v]);
    }
    if (low[u]!= dfn[u]) return ;
    int v; scc[0]++;
    do { v= s.top(), s.pop(), scc[v]= scc[0], vis[v]= 0, siz[scc[0]]++; } while (v!= u);
}
int ans, dis[N], rev[N], pt, mx[N], vv[N], sum[N];
void dfs( int u, int fu) { 
	rev[++pt]= u; for ( int i= head[u], v; i; i= E[i].nxt) if ((v= E[i].to)!= fu&& ! vis[v]) dis[v]= dis[u]+ E[i].w, dfs(v, u); 
}
void dfs2( int u, int ed) {
	vv[u]= 1, rev[++pt]= u;
	for ( int i= head[u], v; i; i= E[i].nxt) { v= E[i].to; if (vis[v]&& ! vv[v]) dfs2(v, ed); } 
}
int mxx[N<< 2];
void build( int k, int l, int r) {
	mxx[k]= -inf; int mid= (l+ r)>> 1;
	if (l== r) return mxx[k]= mx[rev[l]]+ sum[l], void();
	build(k* 2, l, mid), build(k* 2+ 1, mid+ 1, r);
	mxx[k]= max(mxx[k* 2], mxx[k* 2+ 1]);
}
int ask( int k, int l, int r, int x, int y) {
	if (x<= l&& r<= y) return mxx[k];
	int mid= (l+ r)>> 1, res= -inf;
	if (x<= mid) res= max(res, ask(k* 2, l, mid, x, y));
	if (y> mid) res= max(res, ask(k* 2+ 1, mid+ 1, r, x, y));
	return res; 
}
int solve( int cir) {
	int res= 0;
	for ( auto u: circle[cir]) {
		vis[u]= 0;
		int id1= 0; pt= 0, dfs(u, 0);
		for ( int i= 1, v= rev[i]; i<= pt; i++, v= rev[i]) id1= (dis[id1]< dis[v]? v: id1), mx[u]= dis[id1], dis[v]= 0;
		pt= 0, dfs(id1, 0);
		for ( int i= 1, v= rev[i]; i<= pt; i++, v= rev[i]) res= max(res, dis[v]), dis[v]= 0;
		vis[u]= 1;
	}
	pt= 0, dfs2(circle[cir][0], circle[cir][0]);
//	for ( int i= 1, v= rev[i]; i<= pt; i++, v= rev[i]) cout<<v<<" ";
//	cout<<endl;
	for ( int i= 1, v= rev[i]; i<= pt; i++, v= rev[i]) vv[v]= 0;
	for ( int i= pt+ 1; i<= pt* 2; i++) rev[i]= rev[i- pt];
	for ( int i= 2, v= rev[i]; i<= pt* 2; i++, v= rev[i]) sum[i]= sum[i- 1]+ (mp.count({rev[i- 1], v})? mp[{rev[i- 1], v}]: mp[{v, rev[i- 1]}]);
//	for ( int i= 1, v= rev[i]; i<= pt*2; i++, v= rev[i]) cout<<v<<" "<<sum[i]<<endl;
	build(1, 1, pt* 2);
	for ( int l= 1; l+ pt- 1<= pt* 2; l++) {
		int r= l+ pt- 1, s= mx[rev[l]]- sum[l];
		res= max(res, s+ ask(1, 1, pt* 2, l, r));
	}
	return res;
}
signed main() {
	n= read();
	for ( int i= 1, u, l; i<= n; i++) u= read(), l= read(), add(i, u, l), add(u, i, l), mp[{i, u}]= l;
	for ( int i= 1; i<= n; i++) if (! dfn[i]) tarjan(i);
	for ( int i= 1; i<= scc[0]; i++) if (siz[i]> 1) { ++cnt; for ( int j= 1; j<= n; j++) if (scc[j]== i) circle[cnt].push_back(j); }
	memset(vis, 0, sizeof vis);
	for ( int i= 1; i<= cnt; i++) for ( auto v: circle[i]) vis[v]=1;
	for ( int i= 1; i<= cnt; i++) ans+= solve(i);
	cout<<ans;
}