#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
const int mxN=2e5;
int n, dp[mxN][4];
vector<pii> adj[mxN];
void dfs1(int u, int p, int a) {
int m1=0, m2=0, m3=0, mi1=-1, mi2, mi3=-1, mi4;
for(pii e : adj[u]) {
int v=e.fi;
if(v==p)
continue;
dfs1(v, u, e.se);
dp[u][0]+=dp[v][0];
m1=max(dp[v][2]-dp[v][0]+a, m1);
m2=max(dp[v][1]-dp[v][0], m2);
m3=max(dp[v][3]-dp[v][0]+a, m3);
if(mi1==-1||dp[v][2]-dp[v][0]>dp[mi1][2]-dp[mi1][0]) {
mi2=mi1;
mi1=v;
} else if(mi2==-1||dp[v][2]-dp[v][0]>dp[mi2][2]-dp[mi2][0])
mi2=v;
if(mi3==-1||dp[v][3]-dp[v][0]>dp[mi3][3]-dp[mi3][0]) {
mi4=mi3;
mi3=v;
} else if(mi4==-1||dp[v][3]-dp[v][0]>dp[mi4][3]-dp[mi4][0])
mi4=v;
}
dp[u][2]=dp[u][0]+a;
dp[u][1]=dp[u][0]+m2;
// cout << mi1 << " " << mi2 << " " << mi3 << " " << mi4 << endl;
if(mi1!=-1&&mi3!=-1)
dp[u][1]=max(dp[u][0]+(mi1!=mi3?dp[mi1][2]-dp[mi1][0]+dp[mi3][3]-dp[mi3][0]:max(mi2==-1?0:dp[mi2][2]-dp[mi2][0]+dp[mi3][3]-dp[mi3][0], mi4==-1?0:dp[mi1][2]-dp[mi1][0]+dp[mi4][3]-dp[mi4][0])), dp[u][1]);
dp[u][3]=dp[u][1]+a;
dp[u][1]=max(dp[u][0]+m3, dp[u][1]);
dp[u][0]+=m1;
// cout << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << " " << dp[u][3] << " " << u << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n-1; ++i) {
int u, v, c;
cin >> u >> v >> c, --u, --v;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
dfs1(0, -1, -2e9);
cout << dp[0][1];
}
Compilation message
beads.cpp: In function 'void dfs1(int, int, int)':
beads.cpp:38:179: warning: 'mi4' may be used uninitialized in this function [-Wmaybe-uninitialized]
dp[u][1]=max(dp[u][0]+(mi1!=mi3?dp[mi1][2]-dp[mi1][0]+dp[mi3][3]-dp[mi3][0]:max(mi2==-1?0:dp[mi2][2]-dp[mi2][0]+dp[mi3][3]-dp[mi3][0], mi4==-1?0:dp[mi1][2]-dp[mi1][0]+dp[mi4][3]-dp[mi4][0])), dp[u][1]);
~~~~~~~~~^
beads.cpp:38:102: warning: 'mi2' may be used uninitialized in this function [-Wmaybe-uninitialized]
dp[u][1]=max(dp[u][0]+(mi1!=mi3?dp[mi1][2]-dp[mi1][0]+dp[mi3][3]-dp[mi3][0]:max(mi2==-1?0:dp[mi2][2]-dp[mi2][0]+dp[mi3][3]-dp[mi3][0], mi4==-1?0:dp[mi1][2]-dp[mi1][0]+dp[mi4][3]-dp[mi4][0])), dp[u][1]);
~~~~~~~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
5036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
5036 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4988 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
24 ms |
4992 KB |
Output is correct |
19 |
Correct |
9 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
5036 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4988 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
24 ms |
4992 KB |
Output is correct |
19 |
Correct |
9 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
4992 KB |
Output is correct |
23 |
Correct |
9 ms |
5376 KB |
Output is correct |
24 |
Correct |
9 ms |
5248 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
10 ms |
5504 KB |
Output is correct |
27 |
Correct |
10 ms |
5504 KB |
Output is correct |
28 |
Correct |
10 ms |
5632 KB |
Output is correct |
29 |
Correct |
10 ms |
5632 KB |
Output is correct |
30 |
Correct |
11 ms |
5644 KB |
Output is correct |
31 |
Correct |
11 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
5120 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
6 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
5 ms |
5120 KB |
Output is correct |
8 |
Correct |
7 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
5036 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4988 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
24 ms |
4992 KB |
Output is correct |
19 |
Correct |
9 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
4992 KB |
Output is correct |
23 |
Correct |
9 ms |
5376 KB |
Output is correct |
24 |
Correct |
9 ms |
5248 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
10 ms |
5504 KB |
Output is correct |
27 |
Correct |
10 ms |
5504 KB |
Output is correct |
28 |
Correct |
10 ms |
5632 KB |
Output is correct |
29 |
Correct |
10 ms |
5632 KB |
Output is correct |
30 |
Correct |
11 ms |
5644 KB |
Output is correct |
31 |
Correct |
11 ms |
6016 KB |
Output is correct |
32 |
Correct |
37 ms |
7636 KB |
Output is correct |
33 |
Correct |
32 ms |
7672 KB |
Output is correct |
34 |
Correct |
39 ms |
7672 KB |
Output is correct |
35 |
Correct |
232 ms |
15740 KB |
Output is correct |
36 |
Correct |
208 ms |
15736 KB |
Output is correct |
37 |
Correct |
217 ms |
15852 KB |
Output is correct |
38 |
Correct |
157 ms |
16112 KB |
Output is correct |
39 |
Correct |
132 ms |
16092 KB |
Output is correct |
40 |
Correct |
150 ms |
15840 KB |
Output is correct |
41 |
Correct |
198 ms |
20308 KB |
Output is correct |