RT, 调了好久。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n, vis[N];
int top, lst, exists, cnt, ctt, cir[N], stk[N];
long long res, ans, d[N], dp[2 * N], s[N], edg[N];
int h, t, q[N];
struct EDGE {
	int v;	
	long long w;
} ;
vector <EDGE> G[N];

inline void debug (long long a[], int n) {
	cout << "de :\n";
	for (int i = 1; i <= n; i ++) cout << a[i] << " ";
	cout << endl;
}
inline void dedbug (int a[], int n) {
	cout << "de :\n";
	for (int i = 1; i <= n; i ++) cout << a[i] << " ";
	cout << endl;
}
inline void add (int u, int v, int w) { G[u].push_back(EDGE{v, w}); }
inline void get_loop (int u, int fa, int dis) {
	vis[u] = 1, stk[++ top] = u, edg[top] = dis;
	for (auto e : G[u]) {
		int v = e.v, w = e.w;
		if (exists) return ;
		if (v == fa) continue ;
		if (vis[v]) {
			exists = 1, lst = w;
			while (stk[top] != v) 
				cir[++ cnt] = stk[top --];
			cir[++ cnt] = v;
			reverse(cir + 1, cir + 1 + cnt);
			for (int i = 1; i <= cnt; i ++)
				s[i] = s[i - 1] + edg[i];
			return ;
		}
		get_loop(v, u, w);
	}
	top --, vis[u] = 0;
}
inline void dfs (int u) {
	if (! vis[u]) ctt ++;
	vis[u] = 1;
	for (auto e : G[u]) {
		int v = e.v, w = e.w;
		if (vis[v]) continue ;
		dfs(v); // 记得底艾弗埃斯
		ans = max(ans, d[u] + d[v] + w), d[u] = max(d[u], d[v] + w);
	}
}
inline long long solve (int u) {
	cnt = exists = top = 0, get_loop(u, 0, 0);
	long long res1 = 0, res2 = 0;
	for (int i = 1; i <= cnt; i ++) {
		ans = 0, dfs(cir[i]);
		res1 = max(res1, ans);
		s[i + cnt] = s[i], cir[i + cnt] = cir[i];
	}
	if (! cnt) {
		ctt = 0, dfs(u), res1 = d[u];	
		if (ctt == 2) {
			for (auto e : G[u])
				for (auto ee : G[e.v])
					res1 = max(res1, ee.w);
		} 
	} 
	edg[1] = lst;
	for (int i = cnt + 1; i <= 2 * cnt; i ++)
		s[i] = s[i - 1] + edg[i - cnt];
	q[h = t = 1] = 1;
	for (int i = 2; i <= 2 * cnt; i ++) {
		while (h <= t && q[h] <= i - cnt) h ++;
		res2 = max(res2, d[cir[i]] + d[cir[q[h]]] + s[i] - s[q[h]]);
		while (h <= t && d[cir[q[t]]] - s[q[t]] <= d[cir[i]] - s[i]) t --;
		q[++ t] = i;
	}
	return max(res1, res2);
}
signed main () {
	cin >> n;
	for (int i = 1, v; i <= n; i ++) {
		long long w;
		scanf("%d %lld", & v, & w);
		add(i, v, w), add(v, i, w);
	}
	for (int i = 1; i <= n; i ++)
		if (! vis[i]) res += solve(i);
	cout << res;
	return 0;
}