/*
*
* 思路:
* 题目中说了每一个点都有一条出边,所以这个图一定是一个基环树森林,
* 首先找到基环树森林中所有的环,环上的每一个树都用树形DP求树上任意两点的最大距离
* 每个树形DP返回该树上离环上的根节点最远的节点的距离,作为该根的权值,然后剩下再求
* 跨环的两点间的最远距离,其实就是求环上任意两点间距离加上环上点的权值的最大值,将环
* 破开成两倍长度的序列,问题可以结合前缀和转换成一个滑动窗口极值问题求解,每一棵基环
* 树上两点的最大距离是跨环的最大距离和不跨环的最大距离两类距离的最大值,两类分别求解,
* 最后把每一棵基环树的最大距离加起来,就是最后的答案
*
*
*/
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <deque>
using namespace std;
const int N = 1000005;
const int M = N * 2;
int next_node[N]; // 有向边的下一个点
long long next_node_len[N]; // 有向边的长度
int visit[N];
int processed[N];
int path[N];
int last_pos[N]; // 每一个节点最后一次出现在path中的位置
int on_circle[N]; // 点是否在环上
int path_pos;
int NN;
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int cc[N*2]; // 破环之后的序列
long long S[N*2]; // 破环之后距离的前缀和
long long wei[N*2]; // wei[i]表示破环之后,环上第i个点为根的树上的两点间最大距离
long long tot_ans = 0;
// 树上dp求树上任意两点之间的最大距离
long long dp(int root, int prev, long long& max_length) {
long long major = 0, minor = 0;
long long max_val = 0;
for (int e_idx = h[root]; ~e_idx; e_idx = ne[e_idx]) {
int node = e[e_idx];
long long length = (long long)w[e_idx];
if (node == prev || on_circle[node]) {
continue;
}
long long val = length + dp(node, root, max_length);
if (val > major) {
minor = major;
major = val;
} else {
if (val > minor) {
minor = val;
}
}
max_val = max(max_val, val);
}
max_length = max(max_length, major + minor);
return max_val;
}
// 处理path中start到end表示的环, 返回该环代表的基环树上的两点之间的最大距离
long long solve(int start, int end) {
for (int i = start; i <= end; i++) {
on_circle[path[i]] = 1;
}
if (end == start + 1) {
// 只有两个点的环相当于无向边有重边,特殊处理
long long ret = 0;
long long len1 = dp(path[start], 0, ret);
long long len2 = dp(path[end], 0, ret);
ret = max(ret, len1 + len2 + max(next_node_len[path[start]], next_node_len[path[end]]));
return ret;
}
int n = end - start + 1;
for (int i = start; i <= end; i++) {
cc[i-start] = cc[i-start+n] = path[i];
}
// 环上的每一棵树都进行树上dp
long long max_length = 0;
for (int i = start; i <= end ; i++) {
long long val = dp(path[i], 0, max_length);
wei[i-start] = wei[i-start+n] = val;
}
// 跨环的点的最长距离用长度是n-1的滑动窗口求解
S[0] = 0;
for (int i = 1; i < 2*n; i++) {
long long length = 0;
int a = cc[i-1], b = cc[i];
if (next_node[a] == b) {
length = max(length, next_node_len[a]);
}
if (next_node[b] == a) {
length = max(length, next_node_len[b]);
}
S[i] = S[i-1] + length;
}
deque<pair<long long, int>> que;
for (int i = 0; i < 2*n; i++) {
long long val = S[i] + wei[i];
while (que.size() > 0 && que[0].first <= val) {
que.pop_front();
}
que.push_front(pair<long long, int>{val, i});
while (que.size() > 0 && que[que.size()-1].second <= i - (n-1)) {
que.pop_back();
}
if (i >= n-1) {
max_length = max(max_length, wei[i-n+1] - S[i-n+1] + que[que.size()-1].first);
}
}
return max_length;
}
// dfs找环
bool flag = false; // 当前是否已经找到一个环
void dfs(int cur, int prev) {
visit[cur] = 1;
processed[cur] = 1;
path[path_pos++] = cur;
last_pos[cur] = path_pos-1;
for (int e_idx = h[cur]; ~e_idx; e_idx = ne[e_idx]) {
int nei = e[e_idx];
if (nei == prev) {
// 环上只有两个点,特殊处理
if (next_node[prev] == cur && next_node[cur] == prev) {
if (!flag) {
long long ret = solve(path_pos - 2, path_pos - 1);
tot_ans += ret;
flag = true;
}
}
} else {
if (visit[nei]) {
if (!flag) {
long long ret = solve(last_pos[nei], path_pos-1);
tot_ans += ret;
flag = true;
}
} else {
dfs(nei, cur);
}
}
}
visit[cur] = 0;
path_pos--;
}
int main(void) {
//freopen("/Users/grh/Programming/CLionProjects/SimpleTest/input.txt", "r", stdin);
int n;
int b;
long long ww;
memset(h, -1, sizeof h);
scanf("%d", &n);
NN = n;
for (int i = 1; i<= n; i++) {
scanf("%d %lld", &b, &ww);
next_node[i] = b;
next_node_len[i] = ww;
add(i, b, ww);
add(b, i, ww);
}
for (int i = 1; i <= n; i++) {
if (!processed[i]) {
flag = false;
dfs(i, 0);
}
}
printf("%lld\n", tot_ans);
return 0;
}