#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
const int mxN = 2e5 + 10;
int n;
vector<vector<pair<int, int>>> adj(mxN);
int dp[mxN][2];
void dfs(int u, int fu) {
vector<int> g;
dp[u][0] = 0;
dp[u][1] = - INF;
int sum = 0;
for(auto [v, w] : adj[u]) {
if(v == fu) continue ;
dfs(v, u);
sum += max(dp[v][0], dp[v][1] + w);
g.push_back((dp[v][0] + w) - max(dp[v][0], dp[v][1] + w));
}
sort(g.begin(), g.end(), greater<int> ());
dp[u][0] = max(dp[u][0], sum);
if(g.size() > 1) dp[u][0] = max(dp[u][0], sum + g[0] + g[1]);
if(g.size() > 0) dp[u][1] = max(dp[u][1], sum + g[0]);
}
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 << dp[1][0] << "\n";
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for(auto [v, w] : adj[u]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4952 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4952 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4952 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4952 KB |
Output is correct |
3 |
Correct |
1 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
1 ms |
4952 KB |
Output is correct |
6 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |