#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int dydis = 1e6 + 100;
const long long inf = 1000000000000000000;
int n;
int ind;
long long opcija, pries, pgl, delta;
vector<pair<int, int> > grafas[dydis];
int gr[dydis] = {0};
int wh[dydis] = {0};
bool vis[dydis] = {0};
bool visited[dydis] = {0};
bool inCycle[dydis] = {0};
long long cycVal[dydis] = {0};
long long pref[dydis], suf[dydis];
multiset<long long> pirmas, antras;
void dfs(int v, int prim) {
queue<int> q;
q.push(v);
while (!q.empty()) {
v = q.front();
q.pop();
if (visited[v]) {
continue;
}
visited[v] = 1;
for (auto x : grafas[v]) {
if (visited[x.first]) {
continue;
}
q.push(x.first);
}
}
}
vector<int> cNodes, cNodes1;
bool fd = 0;
void findCycle(int v) {
if (fd) {
return;
}
if (vis[v]) {
cNodes.push_back(v);
fd = 1;
return;
}
if (!fd) {
cNodes.push_back(v);
}
vis[v] = 1;
findCycle(gr[v]);
if (!fd) {
cNodes.pop_back();
}
}
long long otherVal = 0;
long long dfs1(int v, int came) {
long long ret = 0;
long long mx1 = 0;
long long mx2 = 0;
for (auto x : grafas[v]) {
if (x.first == came) {
continue;
}
long long opcija = dfs1(x.first, v) + x.second;
if (opcija > mx1) {
mx2 = mx1;
mx1 = opcija;
}
else if (opcija > mx2) {
mx2 = opcija;
}
ret = max(ret, opcija);
}
otherVal = max(otherVal, mx1 + mx2);
return ret;
}
void removeVal(multiset<long long> &st, long long val) {
auto itr = st.find(val);
if (itr != st.end()) {
st.erase(itr);
}
}
bool yraKairej[dydis] = {0};
long long sm1, sm2, st, atsak, mx1, mx2, sum, m;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
a--;
gr[i] = a;
wh[i] = b;
grafas[a].push_back({i, b});
grafas[i].push_back({a, b});
}
atsak = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) {
continue;
}
dfs(i, i);
cNodes1.clear();
cNodes.clear();
fd = 0;
findCycle(i);
bool can = 0;
for (auto x : cNodes) {
if (x == cNodes.back()) {
can = 1;
}
if (can) {
cNodes1.push_back(x);
}
}
cNodes1.pop_back();
for (auto x : cNodes1) {
inCycle[x] = 1;
}
otherVal = 0;
for (auto x : cNodes1) {
cycVal[x] = 0;
mx1 = 0, mx2 = 0;
for (auto y : grafas[x])
if (!inCycle[y.first]) {
opcija = dfs1(y.first, x) + y.second;
cycVal[x] = max(cycVal[x], opcija);
if (opcija > mx1) {
mx2 = mx1;
mx1 = opcija;
}
else if (opcija > mx2) {
mx2 = opcija;
}
otherVal = max(otherVal, mx1 + mx2);
}
}/*
cout << i << " cycle = ";
for(auto x : cNodes1){
cout << "{" << x << ", " << cycVal[x] << "} ";
}
cout << endl << endl;*/
sum = 0;
for (auto x : cNodes1) {
sum += wh[x];
}
m = cNodes1.size();
st = 0;
pref[0] = 0;
suf[m - 1] = 0;
for (int j = 1; j < m; j++) {
pref[j] = pref[j - 1] + wh[cNodes1[j - 1]];
}
for (int j = m - 2; j > -1; j--) {
suf[j] = suf[j + 1] + wh[cNodes1[j]];
}
// ats1 = mas[i] + mas[j] + pref[j] - pref[i]
// ats1 = (mas[i] - pref[i]) + (mas[j]+pref[j])
//
// ats2 = (pref[i] + mas[i] + x) + suf[j] + mas[j]
for (int j = 0; j < m; j++) {
pirmas.insert(cycVal[cNodes1[j]] + pref[j]);
antras.insert(cycVal[cNodes1[j]] + suf[j]);
}
for (int j = 0; j < m - 1; j++) {
removeVal(pirmas, cycVal[cNodes1[j]] + pref[j]);
removeVal(antras, cycVal[cNodes1[j]] + suf[j]);
did1 = (*pirmas.rbegin()) + cycVal[cNodes1[j]] - pref[j];
did2 = (*antras.rbegin()) + pref[j] + wh[cNodes1[m - 1]] + cycVal[cNodes1[j]];
st = max(st, max(did1, did2));
}
removeVal(pirmas, cycVal[cNodes1[m - 1]] + pref[m - 1]);
removeVal(antras, cycVal[cNodes1[m - 1]] + suf[m - 1]);
st = max(st, otherVal);
atsak += st;
// cout << "DONE" << endl << endl << endl;
}
cout << atsak;
return 0;
}
/*
* 1) kai pridedu nauja node'a, jo reiksme bus atstumas iki pirmosios (pagal laikr. ) + cycVal[x]
* 2) kai pasalinu nauja node'a, jo reiksme bus
*
*/
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:215:17: error: 'did1' was not declared in this scope
215 | did1 = (*pirmas.rbegin()) + cycVal[cNodes1[j]] - pref[j];
| ^~~~
islands.cpp:216:17: error: 'did2' was not declared in this scope
216 | did2 = (*antras.rbegin()) + pref[j] + wh[cNodes1[m - 1]] + cycVal[cNodes1[j]];
| ^~~~
