#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000001;
vector<pair<int, int>> adj[N];
int deg[N], lv[N];
bool cycle[N], vis[N];
ll dp[2][N], qs[N], a[N];
ll res = 0;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
int a, x;
cin >> a >> x;
adj[i].push_back({ a, x });
adj[a].push_back({ i, x });
deg[i]++, deg[a]++;
}
// find cycle using kahn's algorithm
{
queue<int> q;
for (int i = 1;i <= n;i++) {
cycle[i] = 1;
if (deg[i] == 1) q.push(i);
}
while (!q.empty()) {
int v = q.front();
q.pop();
cycle[v] = 0;
for (auto& x : adj[v]) {
if (deg[x.first] > 1) {
lv[x.first] = max(lv[x.first], lv[v] + 1);
}
if (--deg[x.first] == 1) q.push(x.first);
}
}
}
//for (int i = 1;i <= n;i++) cout << lv[i] << ' ';
ll ans = 0;
// for each component find the longest path and sum up to answer
for (int i = 1;i <= n;i++) {
if (!cycle[i] || vis[i]) continue;
vector<pair<int, int>> c;
c.push_back({ 0, 0 });
int now = i, p = -1;
while (1) {
bool ch = 0;
vis[now] = 1;
for (auto& x : adj[now]) {
if (!cycle[x.first] || x.first == p) continue;
c.push_back({ now, x.second });
if (!vis[x.first]) {
p = now;
ch = 1;
now = x.first;
break;
}
}
if (!ch) {
if ((int)c.size() == 2) { // parallel edge
multiset<int> s;
for (auto& x : adj[now]) {
if (!cycle[x.first]) continue;
s.insert(x.second);
}
s.erase(s.find(c.back().second));
c.push_back({ now, *s.begin() });
}
break;
}
}
// c is list of cycle in order
{ // dp on tree
for (auto& x : c) vis[x.first] = 0;
// bfs
vector<int> nodes;
queue<int> q;
q.push(i), vis[i] = 1;
while (!q.empty()) {
int v = q.front();
q.pop();
nodes.push_back(v);
for (auto& x : adj[v]) if (!vis[x.first]) q.push(x.first), vis[x.first] = 1;
}
sort(nodes.begin(), nodes.end(), [&](int a, int b) {
return lv[a] < lv[b];
});
for (auto& v : nodes) {
dp[0][v] = dp[1][v] = 0;
for (auto& x : adj[v]) {
if (lv[x.first] > lv[v] || cycle[x.first]) continue;
dp[1][v] = max(dp[1][v], dp[0][x.first] + x.second);
if (dp[1][v] > dp[0][v]) swap(dp[0][v], dp[1][v]);
}
res = max(res, dp[0][v] + dp[1][v]);
}
}
int sz = c.size() - 1;
res = 0;
for (int i = 1;i <= sz;i++) {
qs[i] = qs[i - 1] + c[i - 1].second;
a[i] = dp[0][c[i].first];
}
ll mx = -1e18, mx2 = -1e18;
ll sk = c[sz].second;
for (int i = 1;i <= sz;i++) {
res = max(res, mx + qs[i] + a[i]);
res = max(res, mx2 + qs[sz] - qs[i] + a[i] + sk);
mx = max(mx, -qs[i] + a[i]);
mx2 = max(mx2, qs[i] + a[i]);
}
ans += res;
//cout << res << ' ';
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
23900 KB |
Output isn't correct |
| 3 |
Correct |
13 ms |
23900 KB |
Output is correct |
| 4 |
Correct |
10 ms |
23900 KB |
Output is correct |
| 5 |
Correct |
10 ms |
24004 KB |
Output is correct |
| 6 |
Correct |
10 ms |
23900 KB |
Output is correct |
| 7 |
Correct |
9 ms |
23900 KB |
Output is correct |
| 8 |
Correct |
10 ms |
24004 KB |
Output is correct |
| 9 |
Correct |
10 ms |
23968 KB |
Output is correct |
| 10 |
Incorrect |
10 ms |
23900 KB |
Output isn't correct |
| 11 |
Correct |
10 ms |
23900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24052 KB |
Output is correct |
| 2 |
Correct |
16 ms |
24192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25180 KB |
Output is correct |
| 2 |
Correct |
21 ms |
27024 KB |
Output is correct |
| 3 |
Correct |
17 ms |
25744 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
24668 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
28352 KB |
Output is correct |
| 2 |
Correct |
33 ms |
31792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
40012 KB |
Output is correct |
| 2 |
Correct |
64 ms |
41644 KB |
Output is correct |
| 3 |
Correct |
79 ms |
46948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
53936 KB |
Output is correct |
| 2 |
Correct |
140 ms |
68068 KB |
Output is correct |
| 3 |
Correct |
148 ms |
70912 KB |
Output is correct |
| 4 |
Correct |
180 ms |
82784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
112132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
100296 KB |
Output is correct |
| 2 |
Incorrect |
228 ms |
100020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
