#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
int n;
vector<vector<pair<int, int>>> adj(mxN);
int cost[mxN];
int dp[mxN][2][2];
void dfs(int u, int fu) {
if(adj[u].size() == 1 && fu != -1) return ;
vector<pair<int, int>> L, R;
int sum = 0, A = 0;
for(auto [v, w] : adj[u]) if(v != fu) {
cost[v] = w;
dfs(v, u);
int x = max(dp[v][0][0], dp[v][0][1]);
sum += x;
int y = max(dp[v][1][0], dp[v][1][1]);
int newA = y - x;
A = max(A, newA);
L.push_back({dp[v][0][0] + w - x, v});
R.push_back({dp[v][1][0] + w - x, v});
}
sort(L.begin(), L.end(), greater<pair<int, int>> ());
sort(R.begin(), R.end(), greater<pair<int, int>> ());
dp[u][0][0] = sum;
dp[u][1][0] = sum + A;
if(L.size() > 1)
dp[u][1][0] = max(dp[u][1][0], sum + L[0].first + L[1].first);
if(L[0].second != R[0].second) {
dp[u][1][0] = max(dp[u][1][0], sum + L[0].first + R[0].first);
} else if(L.size() > 1) {
dp[u][1][0] = max(dp[u][1][0], sum + L[0].first + R[1].first);
dp[u][1][0] = max(dp[u][1][0], sum + L[1].first + R[0].first);
}
dp[u][0][1] = sum + cost[u] + L[0].first;
dp[u][1][1] = sum + cost[u] + R[0].first;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n - 1; i ++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1, -1);
cout << max(dp[1][0][0], dp[1][1][0]) << "\n";
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for(auto [v, w] : adj[u]) if(v != fu) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
5112 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
2 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4952 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
5112 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
2 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4952 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
4956 KB |
Output is correct |
14 |
Correct |
2 ms |
4956 KB |
Output is correct |
15 |
Correct |
2 ms |
4956 KB |
Output is correct |
16 |
Correct |
2 ms |
4952 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
2 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Correct |
2 ms |
4956 KB |
Output is correct |
21 |
Correct |
2 ms |
4956 KB |
Output is correct |
22 |
Correct |
2 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
5112 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
2 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4952 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
4956 KB |
Output is correct |
14 |
Correct |
2 ms |
4956 KB |
Output is correct |
15 |
Correct |
2 ms |
4956 KB |
Output is correct |
16 |
Correct |
2 ms |
4952 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
2 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Correct |
2 ms |
4956 KB |
Output is correct |
21 |
Correct |
2 ms |
4956 KB |
Output is correct |
22 |
Correct |
2 ms |
4956 KB |
Output is correct |
23 |
Correct |
3 ms |
5468 KB |
Output is correct |
24 |
Correct |
4 ms |
5468 KB |
Output is correct |
25 |
Correct |
3 ms |
5468 KB |
Output is correct |
26 |
Correct |
5 ms |
5892 KB |
Output is correct |
27 |
Correct |
5 ms |
5900 KB |
Output is correct |
28 |
Correct |
6 ms |
6212 KB |
Output is correct |
29 |
Correct |
7 ms |
5900 KB |
Output is correct |
30 |
Correct |
5 ms |
6176 KB |
Output is correct |
31 |
Correct |
6 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
5112 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
2 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
1 ms |
4952 KB |
Output is correct |
12 |
Correct |
1 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
4956 KB |
Output is correct |
14 |
Correct |
2 ms |
4956 KB |
Output is correct |
15 |
Correct |
2 ms |
4956 KB |
Output is correct |
16 |
Correct |
2 ms |
4952 KB |
Output is correct |
17 |
Correct |
1 ms |
4956 KB |
Output is correct |
18 |
Correct |
2 ms |
4956 KB |
Output is correct |
19 |
Correct |
1 ms |
4956 KB |
Output is correct |
20 |
Correct |
2 ms |
4956 KB |
Output is correct |
21 |
Correct |
2 ms |
4956 KB |
Output is correct |
22 |
Correct |
2 ms |
4956 KB |
Output is correct |
23 |
Correct |
3 ms |
5468 KB |
Output is correct |
24 |
Correct |
4 ms |
5468 KB |
Output is correct |
25 |
Correct |
3 ms |
5468 KB |
Output is correct |
26 |
Correct |
5 ms |
5892 KB |
Output is correct |
27 |
Correct |
5 ms |
5900 KB |
Output is correct |
28 |
Correct |
6 ms |
6212 KB |
Output is correct |
29 |
Correct |
7 ms |
5900 KB |
Output is correct |
30 |
Correct |
5 ms |
6176 KB |
Output is correct |
31 |
Correct |
6 ms |
6744 KB |
Output is correct |
32 |
Correct |
19 ms |
8792 KB |
Output is correct |
33 |
Correct |
19 ms |
8792 KB |
Output is correct |
34 |
Correct |
20 ms |
8792 KB |
Output is correct |
35 |
Correct |
129 ms |
20044 KB |
Output is correct |
36 |
Correct |
103 ms |
20052 KB |
Output is correct |
37 |
Correct |
103 ms |
19880 KB |
Output is correct |
38 |
Correct |
107 ms |
25280 KB |
Output is correct |
39 |
Correct |
95 ms |
20976 KB |
Output is correct |
40 |
Correct |
100 ms |
22928 KB |
Output is correct |
41 |
Correct |
130 ms |
31224 KB |
Output is correct |