#include <iostream>
#include <vector>
using namespace std;
#define endl "\n"
#define ll long long
const ll inf = 1e9 + 69;
const int MX = 200005;
int n;
ll parw[MX], dp[MX][2][2];
vector<pair<int, ll> > adj[MX];
void dfs(int nw, int bf = -1){
if(adj[nw].size() == 1 && bf != -1) return;
ll res = 0ll;
ll best_par_mid = -inf;
ll best_mid = -inf, best_mid2 = -inf;
int best_mid_child, best_mid2_child;
ll best_nomid = -inf, best_nomid2 = -inf;
int best_nomid_child, best_nomid2_child;
for(pair<int, ll> i : adj[nw]) if(i.first != bf){
int nx = i.first; ll wt = i.second;
parw[nx] = wt;
dfs(nx, nw);
ll nomidv = max(dp[nx][0][0], dp[nx][1][0]),
midv = max(dp[nx][0][1], dp[nx][1][1]) - nomidv;
res += nomidv;
if(best_par_mid < midv) best_par_mid = midv;
ll unuse_midv = dp[nx][0][1] + wt - nomidv;
if(best_mid < unuse_midv){
best_mid2 = best_mid;
best_mid2_child = best_mid_child;
best_mid = unuse_midv;
best_mid_child = nx;
}else if(best_mid2 < unuse_midv){
best_mid2 = unuse_midv;
best_mid2_child = nx;
}
ll unuse_nomidv = dp[nx][0][0] + wt - nomidv;
if(best_nomid < unuse_nomidv){
best_nomid2 = best_nomid;
best_nomid2_child = best_nomid_child;
best_nomid = unuse_nomidv;
best_nomid_child = nx;
}else if(best_nomid2 < unuse_nomidv){
best_nomid2 = unuse_nomidv;
best_nomid2_child = nx;
}
}
dp[nw][0][0] = res;
dp[nw][0][1] = max(res + max(0ll, best_par_mid), res + best_nomid + best_nomid2);
if(best_mid_child != best_nomid_child)
dp[nw][0][1] = max(dp[nw][0][1], res + best_nomid + best_mid);
else
dp[nw][0][1] = max(dp[nw][0][1], max(res + best_nomid + best_mid2, res + best_nomid2 + best_mid));
dp[nw][1][0] = res + parw[nw] + best_nomid;
dp[nw][1][1] = res + parw[nw] + best_mid;
return;
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n; ll tw;
for(int u, v, i = 1; i < n; i ++){
cin >> u >> v >> tw;
adj[u].push_back({v, tw});
adj[v].push_back({u, tw});
}
dfs(1);
cout << max(dp[1][0][0], dp[1][0][1]) << "\n";
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:20:22: warning: variable 'best_mid2_child' set but not used [-Wunused-but-set-variable]
20 | int best_mid_child, best_mid2_child;
| ^~~~~~~~~~~~~~~
beads.cpp:22:24: warning: variable 'best_nomid2_child' set but not used [-Wunused-but-set-variable]
22 | int best_nomid_child, best_nomid2_child;
| ^~~~~~~~~~~~~~~~~
beads.cpp:61:2: warning: 'best_nomid_child' may be used uninitialized in this function [-Wmaybe-uninitialized]
61 | if(best_mid_child != best_nomid_child)
| ^~
beads.cpp:61:2: warning: 'best_mid_child' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5036 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5012 KB |
Output is correct |
9 |
Correct |
3 ms |
4964 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5036 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5012 KB |
Output is correct |
9 |
Correct |
3 ms |
4964 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5036 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5012 KB |
Output is correct |
9 |
Correct |
3 ms |
4964 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5032 KB |
Output is correct |
23 |
Correct |
6 ms |
5460 KB |
Output is correct |
24 |
Correct |
5 ms |
5548 KB |
Output is correct |
25 |
Correct |
4 ms |
5460 KB |
Output is correct |
26 |
Correct |
7 ms |
6072 KB |
Output is correct |
27 |
Correct |
8 ms |
6064 KB |
Output is correct |
28 |
Correct |
7 ms |
5944 KB |
Output is correct |
29 |
Correct |
6 ms |
5680 KB |
Output is correct |
30 |
Correct |
7 ms |
5972 KB |
Output is correct |
31 |
Correct |
8 ms |
6580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
5036 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5012 KB |
Output is correct |
9 |
Correct |
3 ms |
4964 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5032 KB |
Output is correct |
23 |
Correct |
6 ms |
5460 KB |
Output is correct |
24 |
Correct |
5 ms |
5548 KB |
Output is correct |
25 |
Correct |
4 ms |
5460 KB |
Output is correct |
26 |
Correct |
7 ms |
6072 KB |
Output is correct |
27 |
Correct |
8 ms |
6064 KB |
Output is correct |
28 |
Correct |
7 ms |
5944 KB |
Output is correct |
29 |
Correct |
6 ms |
5680 KB |
Output is correct |
30 |
Correct |
7 ms |
5972 KB |
Output is correct |
31 |
Correct |
8 ms |
6580 KB |
Output is correct |
32 |
Correct |
26 ms |
10260 KB |
Output is correct |
33 |
Correct |
27 ms |
10188 KB |
Output is correct |
34 |
Correct |
26 ms |
10304 KB |
Output is correct |
35 |
Correct |
155 ms |
26512 KB |
Output is correct |
36 |
Correct |
146 ms |
26572 KB |
Output is correct |
37 |
Correct |
153 ms |
26684 KB |
Output is correct |
38 |
Correct |
101 ms |
25908 KB |
Output is correct |
39 |
Correct |
96 ms |
19504 KB |
Output is correct |
40 |
Correct |
101 ms |
25796 KB |
Output is correct |
41 |
Correct |
146 ms |
32596 KB |
Output is correct |