/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#define order curr
using namespace std;
typedef long long ll;
const int N_MAX = 1000000;
int N;
int to[N_MAX + 2], len[N_MAX + 2];
vector <int> adj[N_MAX + 2];
int other (int u, int v) {
return (u == v ? to[u] : u);
}
int par[N_MAX + 2];
int depth[N_MAX + 2];
pair <int, int> backEdge;
int curr[N_MAX + 2];
void dfs (int u) {
depth[u] = 0;
while (u != 0) {
if (curr[u] < (int) adj[u].size()) {
int x = adj[u][curr[u]++];
int v = other(x, u);
if (depth[v] == -1) {
par[v] = x;
depth[v] = depth[u] + 1;
u = v;
} else if (depth[v] > depth[u]) {
backEdge = make_pair(u, x);
}
} else {
u = other(par[u], u);
}
}
}
bitset <N_MAX + 2> root;
ll maxAny[N_MAX + 2];
ll maxDown[N_MAX + 2];
queue <int> q;
//int order[N_MAX + 2];
void compute (int s) {
q.push(s);
depth[s] = 0;
int cnt = 0;
while (q.empty() == false) {
int u = q.front(); q.pop();
order[++cnt] = u;
for (int x : adj[u]) {
int v = other(x, u);
if (depth[v] == -1 && root[v] == false) {
q.push(v);
depth[v] = depth[u] + 1;
}
}
}
for (int i = cnt; i >= 1; i--) {
int u = order[i];
ll maxDown1 = 0, maxDown2 = 0;
for (int x : adj[u]) {
int v = other(x, u);
if (depth[u] < depth[v] && root[v] == false) {
maxAny[u] = max(maxAny[u], maxAny[v]);
maxDown[u] = max(maxDown[u], maxDown[v] + len[x]);
ll here = maxDown[v] + len[x];
if (here >= maxDown1) {
maxDown2 = maxDown1;
maxDown1 = here;
} else if (here > maxDown2) {
maxDown2 = here;
}
}
}
maxAny[u] = max(maxAny[u], maxDown1 + maxDown2);
}
}
int roots[N_MAX + 2];
int group[N_MAX + 2];
int cntRoots;
int cntGroups;
multiset <ll> s;
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int u = 1; u <= N; u++) {
cin >> to[u] >> len[u];
adj[u].push_back(u);
adj[to[u]].push_back(u);
}
fill(depth + 1, depth + N + 1, -1);
for (int u = 1; u <= N; u++) {
if (depth[u] == -1) {
dfs(u);
int v1, x; tie(v1, x) = backEdge;
int v2 = other(x, v1);
swap(v1, v2);
par[v2] = x;
cntGroups++;
int v = v1;
while (v != v2) {
root[v] = true;
roots[++cntRoots] = v;
group[cntRoots] = cntGroups;
v = other(par[v], v);
}
root[v] = true;
roots[++cntRoots] = v;
group[cntRoots] = cntGroups;
}
}
fill(depth + 1, depth + N + 1, -1);
for (int u = 1; u <= N; u++) {
if (root[u] == true) {
compute(u);
}
}
ll answer = 0;
for (int g = 1, i = 1; g <= cntGroups; g++) {
int j = i;
while (j < cntRoots && group[j + 1] == g) {
j++;
}
ll totalLen = 0;
ll maxLen = 0;
for (int k = i; k <= j; k++) {
int u = roots[k];
totalLen += len[par[u]];
maxLen = max(maxLen, maxAny[u]);
}
ll leng = 0;
for (int k = j; k > i; k--) {
int u = roots[k];
leng += len[par[u]];
s.insert(maxDown[u] + leng);
}
ll lazy = 0;
for (int k = i, u = roots[i]; k <= j; k++) {
assert(s.empty() == false);
maxLen = max(maxLen, *s.rbegin() + lazy + maxDown[u]);
s.insert(maxDown[u] - lazy);
lazy += len[par[u]];
u = other(par[u], u);
assert(s.find((maxDown[u] + totalLen) - lazy) != s.end());
s.erase(s.find((maxDown[u] + totalLen) - lazy));
}
answer += maxLen;
s.clear();
i = j + 1;
}
cout << answer << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23820 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23880 KB |
Output is correct |
| 4 |
Correct |
12 ms |
23872 KB |
Output is correct |
| 5 |
Correct |
13 ms |
23876 KB |
Output is correct |
| 6 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23776 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23816 KB |
Output is correct |
| 9 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 10 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 11 |
Correct |
13 ms |
23880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
16 ms |
24256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
24936 KB |
Output is correct |
| 2 |
Correct |
31 ms |
26976 KB |
Output is correct |
| 3 |
Correct |
23 ms |
25224 KB |
Output is correct |
| 4 |
Correct |
16 ms |
24532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
28224 KB |
Output is correct |
| 2 |
Correct |
56 ms |
31500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
38380 KB |
Output is correct |
| 2 |
Correct |
137 ms |
42772 KB |
Output is correct |
| 3 |
Correct |
179 ms |
48736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
52100 KB |
Output is correct |
| 2 |
Correct |
259 ms |
68244 KB |
Output is correct |
| 3 |
Correct |
412 ms |
76112 KB |
Output is correct |
| 4 |
Correct |
434 ms |
87560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
272 ms |
90448 KB |
Output is correct |
| 2 |
Correct |
856 ms |
114524 KB |
Output is correct |
| 3 |
Correct |
317 ms |
80072 KB |
Output is correct |
| 4 |
Correct |
470 ms |
108040 KB |
Output is correct |
| 5 |
Correct |
475 ms |
107904 KB |
Output is correct |
| 6 |
Correct |
1093 ms |
88252 KB |
Output is correct |
| 7 |
Correct |
661 ms |
122844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
316 ms |
90236 KB |
Output is correct |
| 2 |
Correct |
308 ms |
90368 KB |
Output is correct |
| 3 |
Runtime error |
505 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
