#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = 1000005;
const int inf = 1e9 + 5;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n;
vector<pii> g[maxn];
map<pii,ll> kol;
int nxt[maxn];
ll cost[maxn];
int krug_sta = 0;
int krug_end = 0;
int par[maxn];
int visited[maxn];
void dfs1(int v, int p){
par[v] = p;
visited[v] = 1;
for(auto c : g[v]){
int u = c.fi;
ll w = c.se;
if(u == p && !(nxt[p] == v && nxt[v] == p))continue;
if(!visited[u])dfs1(u, v);
else{
if(visited[u] == 1){
krug_sta = u;
krug_end = v;
}
}
}
visited[v] = 2;
}
ll dia = 0;
bool was[maxn];
ll dfs2(int v, ll duz){
was[v] = 1;
ll best = duz;
for(auto c : g[v]){
int u = c.fi;
ll w = c.se;
if(!was[u]){
ll dist = dfs2(u, duz + w);
dia = max(dia, dist + best - 2 * duz);
best = max(best, dist);
}
}
return best;
}
ll rez = 0;
ll pref[maxn];
ll sta[maxn];
void Solve(int x){
dia = 0;
dfs1(x, -1);
vector<int> cycle;
for(int i = krug_end;i != krug_sta; i = par[i]){
cycle.pb(i);
}
cycle.pb(krug_sta);
vector<pii> krug;
ff(i,1,sz(cycle) - 1){
int a = cycle[i - 1];
int b = cycle[i];
int w = (nxt[a] == b ? cost[a] : cost[b]);
ll.pb({a, w});
}
ll w = (nxt[cycle.back()] == cycle[0] ? cost[cycle.back()] : cost[cycle[0]]);
krug.pb({cycle.back(), w});
for(auto c : krug)was[c.fi] = 1;
ff(i,0,sz(krug) - 1)sta[i] = dfs2(krug[i].fi, 0);
int len = sz(krug);
pref[0] = 0;
ff(i,0,len - 1)pref[i + 1] = pref[i] + krug[i].se;
ll zbir = pref[len];
ll mn = -sta[0];
ll mx = sta[0];
ll najv = 0;
ff(i,1,len - 1){
najv = max(najv, pref[i] + sta[i] - mn);
najv = max(najv, zbir + sta[i] - pref[i] + mx);
mn = min(mn, pref[i] - sta[i]);
mx = max(mx, pref[i] + sta[i]);
}
rez += max(najv, dia);
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin >> n;
ff(i,1,n){
int a;
ll b;
cin >> a >> b;
g[i].pb({a, b});
g[a].pb({i, b});
kol[{i, a}] = kol[{a, i}] = b;
nxt[i] = a;
cost[i] = b;
}
ff(i,1,n){
if(!visited[i]){
Solve(i);
}
}
cout << rez << endl;
return 0;
}
/**
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
// probati bojenje sahovski ili slicno
**/
Compilation message
islands.cpp: In function 'void dfs1(int, int)':
islands.cpp:46:6: warning: unused variable 'w' [-Wunused-variable]
46 | ll w = c.se;
| ^
islands.cpp: In function 'void Solve(int)':
islands.cpp:94:5: error: expected unqualified-id before '.' token
94 | ll.pb({a, w});
| ^
islands.cpp:94:15: error: expected primary-expression before ')' token
94 | ll.pb({a, w});
| ^
islands.cpp:93:7: warning: unused variable 'w' [-Wunused-variable]
93 | int w = (nxt[a] == b ? cost[a] : cost[b]);
| ^
