#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
int n;
vector <pair <int, int> > e[N];
int f[N][2], _w[N], g[N][2];
void down(int u, int p) {
for (auto [v, w]: e[u]) {
if (v == p) continue;
down(v, u);
}
int cur[2] = {0, (int)-1e9};
for (auto [v, w]: e[u]) {
if (v == p) continue;
_w[v] = w;
int ncur[2] = {0, (int)-1e9};
for (int i = 0; i < 2; ++i) {
ncur[i] = max(ncur[i], cur[i] + max(f[v][0], f[v][1] + w));
if (i + 1 < 2) ncur[i + 1] = max(ncur[i + 1], cur[i] + f[v][0] + w);
}
for (int i = 0; i < 2; ++i) cur[i] = ncur[i];
}
f[u][0] = cur[0];
f[u][1] = cur[1];
}
int child[N];
int c[N];
int prf[N][2], suf[N][2];
void up(int u, int p) {
int m = 0;
for (auto [v, w]: e[u]) {
if (v == p) continue;
child[++m] = v;
c[m] = w;
}
prf[0][0] = 0;
prf[0][1] = -1e9;
for (int i = 1; i <= m; ++i) {
int v = child[i];
int w = c[i];
prf[i][0] = prf[i - 1][0] + max(f[v][0], f[v][1] + w);
prf[i][1] = prf[i - 1][1] + max(f[v][0], f[v][1] + w);
prf[i][1] = max(prf[i][1], prf[i - 1][0] + f[v][0] + w);
}
suf[m + 1][0] = 0;
suf[m + 1][1] = -1e9;
for (int i = m; i >= 1; --i) {
int v = child[i];
int w = c[i];
suf[i][0] = suf[i + 1][0] + max(f[v][0], f[v][1] + w);
suf[i][1] = suf[i + 1][1] + max(f[v][0], f[v][1] + w);
suf[i][1] = max(suf[i][1], suf[i + 1][0] + f[v][0] + w);
}
for (int i = 1; i <= m; ++i) {
int v = child[i];
g[v][0] = prf[i - 1][0] + suf[i + 1][0] + max(g[u][0], g[u][1] + _w[u]);
g[v][1] = max({prf[i - 1][0] + suf[i + 1][1] + max(g[u][0], g[u][1] + _w[u]), prf[i - 1][1] + suf[i + 1][0] + max(g[u][0], g[u][1] + _w[u])});
if (u != 1) g[v][1] = max(g[v][1], prf[i - 1][0] + suf[i + 1][0] + g[u][0] + _w[u]);
}
for (auto [v, w]: e[u]) {
if (v == p) continue;
up(v, u);
}
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
down(1, 0);
g[1][0] = 0, g[1][1] = -1e9;
up(1, 0);
int ans = 0;
for (int r = 1; r <= n; ++r) {
ans = max(ans, f[r][0] + max(g[r][0], g[r][1] + _w[r]));
}
cout << ans;
}
Compilation message
beads.cpp: In function 'void down(int, int)':
beads.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
20 | for (auto [v, w]: e[u]) {
| ^
beads.cpp:25:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | for (auto [v, w]: e[u]) {
| ^
beads.cpp: In function 'void up(int, int)':
beads.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for (auto [v, w]: e[u]) {
| ^
beads.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for (auto [v, w]: e[u]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5024 KB |
Output is correct |
2 |
Correct |
4 ms |
5036 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
3 ms |
5028 KB |
Output is correct |
5 |
Correct |
3 ms |
4996 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
4988 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5024 KB |
Output is correct |
2 |
Correct |
4 ms |
5036 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
3 ms |
5028 KB |
Output is correct |
5 |
Correct |
3 ms |
4996 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
4988 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
4 ms |
5076 KB |
Output is correct |
17 |
Correct |
3 ms |
5024 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5008 KB |
Output is correct |
20 |
Correct |
3 ms |
4976 KB |
Output is correct |
21 |
Correct |
3 ms |
5028 KB |
Output is correct |
22 |
Correct |
4 ms |
5024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5024 KB |
Output is correct |
2 |
Correct |
4 ms |
5036 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
3 ms |
5028 KB |
Output is correct |
5 |
Correct |
3 ms |
4996 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
4988 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
4 ms |
5076 KB |
Output is correct |
17 |
Correct |
3 ms |
5024 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5008 KB |
Output is correct |
20 |
Correct |
3 ms |
4976 KB |
Output is correct |
21 |
Correct |
3 ms |
5028 KB |
Output is correct |
22 |
Correct |
4 ms |
5024 KB |
Output is correct |
23 |
Correct |
5 ms |
5424 KB |
Output is correct |
24 |
Correct |
7 ms |
5424 KB |
Output is correct |
25 |
Correct |
5 ms |
5332 KB |
Output is correct |
26 |
Correct |
8 ms |
5716 KB |
Output is correct |
27 |
Correct |
8 ms |
5680 KB |
Output is correct |
28 |
Correct |
7 ms |
5936 KB |
Output is correct |
29 |
Correct |
6 ms |
5844 KB |
Output is correct |
30 |
Correct |
8 ms |
5844 KB |
Output is correct |
31 |
Correct |
8 ms |
6200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5024 KB |
Output is correct |
2 |
Correct |
4 ms |
5036 KB |
Output is correct |
3 |
Correct |
3 ms |
5024 KB |
Output is correct |
4 |
Correct |
3 ms |
5028 KB |
Output is correct |
5 |
Correct |
3 ms |
4996 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
4988 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
4 ms |
5076 KB |
Output is correct |
17 |
Correct |
3 ms |
5024 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5008 KB |
Output is correct |
20 |
Correct |
3 ms |
4976 KB |
Output is correct |
21 |
Correct |
3 ms |
5028 KB |
Output is correct |
22 |
Correct |
4 ms |
5024 KB |
Output is correct |
23 |
Correct |
5 ms |
5424 KB |
Output is correct |
24 |
Correct |
7 ms |
5424 KB |
Output is correct |
25 |
Correct |
5 ms |
5332 KB |
Output is correct |
26 |
Correct |
8 ms |
5716 KB |
Output is correct |
27 |
Correct |
8 ms |
5680 KB |
Output is correct |
28 |
Correct |
7 ms |
5936 KB |
Output is correct |
29 |
Correct |
6 ms |
5844 KB |
Output is correct |
30 |
Correct |
8 ms |
5844 KB |
Output is correct |
31 |
Correct |
8 ms |
6200 KB |
Output is correct |
32 |
Correct |
37 ms |
8652 KB |
Output is correct |
33 |
Correct |
45 ms |
8560 KB |
Output is correct |
34 |
Correct |
26 ms |
8620 KB |
Output is correct |
35 |
Correct |
179 ms |
19920 KB |
Output is correct |
36 |
Correct |
198 ms |
20044 KB |
Output is correct |
37 |
Correct |
192 ms |
19968 KB |
Output is correct |
38 |
Correct |
107 ms |
24452 KB |
Output is correct |
39 |
Correct |
109 ms |
22188 KB |
Output is correct |
40 |
Correct |
109 ms |
21620 KB |
Output is correct |
41 |
Correct |
196 ms |
25724 KB |
Output is correct |