This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
using LL = long long;
#define int long long
#define watch(x) cerr << (#x) << " is " << x << endl
vector<bool> vis, cycle;
vector<array<int, 2>> nxt;
LL max_path(const vector<int>& c, const vector<vector<array<int, 3>>>& adj) {
auto find_cycle = [&](auto&& self, int v, int pid = -1) -> bool {
if (vis[v]) return cycle[v] = true;
vis[v] = true;
for (auto [u, w, eid] : adj[v]) {
if (eid == pid) continue;
bool works = self(self, u, eid);
if (works) {
nxt[v] = {u, w};
return cycle[v] ? false : (cycle[v] = true);
}
}
return false;
};
find_cycle(find_cycle, c[0]);
auto path_in_tree = [&](auto&& self, int v, int p = -1) -> array<LL, 2> {
LL ans = 0;
LL who = v;
for (auto [u, w, _] : adj[v]) {
if (u == p || cycle[u]) continue;
auto [a, b] = self(self, u, v);
if (w + a > ans) {
ans = w + a, who = b;
}
}
return {ans, who};
};
auto diam = [&](auto&& self, int v, int p = -1) -> LL {
LL ans = 0;
for (auto [u, w, _] : adj[v]) {
if (cycle[u] || u == p) continue;
ans = max(ans, w + self(self, u, v));
}
return ans;
};
int start = -1;
for (int i : c) if (cycle[i]) start = i;
vector<LL> fs;
vector<LL> ds; ds.push_back(0);
LL ans = 0;
{
int v = start;
LL len = 0;
do {
auto [nv, lw] = nxt[v];
auto [a, b] = path_in_tree(path_in_tree, v);
cycle[v] = false;
ans = max(ans, diam(diam, b));
cycle[v] = true;
fs.push_back(a);
ds.push_back(len += lw);
v = nv;
} while (v != start);
}
int n = fs.size();
for (int i = 0; i < n; ++i) fs.push_back(fs[i]);
for (int i = 1; i < n; ++i) ds.push_back(ds.back() + ds[i] - ds[i-1]);
deque<array<LL, 2>> best;
int until = -1;
for (int i = 0; i < n; ++i) {
for (int j = until+1; j < i+n; ++j) {
if (!best.empty() && best.front()[1] == i-n) best.pop_front();
while (!best.empty() && best.back()[0] <= fs[j]+ds[j]) best.pop_back();
best.push_back({fs[j]+ds[j], j});
until = j;
}
ans = max(ans, fs[i] - ds[i] + best.front()[0]);
}
return ans;
}
int32_t main() {
#ifdef LORENZO
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
vector<vector<array<int, 3>>> adj(n);
for (int i = 0; i < n; ++i) {
int a; cin >> a; --a;
int w; cin >> w;
adj[i].push_back({a, w, i});
adj[a].push_back({i, w, i});
}
vis.assign(n, false);
vector<vector<int>> cc;
auto dfs = [&](auto&& self, int v) -> void {
vis[v] = true;
cc.back().push_back(v);
for (auto [u, _, __] : adj[v]) {
if (!vis[u]) {
self(self, u);
}
}
};
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
cc.push_back(vector<int>(0));
dfs(dfs, i);
}
}
nxt.assign(n, {-1,-1});
vis.assign(n, false);
cycle.assign(n, false);
LL ans = 0;
for (auto& c : cc) {
ans += max_path(c, adj);
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |