#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int dp[N][4];
vector< pair< int,int > > g[N];
void solve(int u,int p = -1)
{
int sum01 = 0,mx = -2e9,mx0 = -2e9,mx1 = -2e9,mx2 = -2e9,mx02 = -2e9,mx3 = -2e9,mx4 = -2e9;
for(auto &x:g[u])
{
if(x.first==p) continue;
solve(x.first,u);
int cut = max(dp[x.first][0],dp[x.first][1]+x.second);
sum01 += cut;
mx = max(mx,dp[x.first][0]-cut+x.second);
if(mx0!=-2e9) mx02 = max(mx02,mx0+max(dp[x.first][0],dp[x.first][2])+x.second-cut);
if(mx2!=-2e9) mx02 = max(mx02,mx2+dp[x.first][0]+x.second-cut);
mx0 = max(mx0,dp[x.first][0]+x.second-cut);
mx1 = max(mx1,max(max(dp[x.first][0],dp[x.first][2]),dp[x.first][1]+x.second)-cut);
mx2 = max(mx2,max(dp[x.first][0],dp[x.first][2])-cut+x.second);
mx3 = max(mx3,dp[x.first][2]-cut+x.second);
mx4 = max(mx4,dp[x.first][3]-cut+x.second);
}
dp[u][0] = sum01,dp[u][1] = sum01+mx,dp[u][2] = sum01+max(mx02,max(mx1,mx4)),dp[u][3] = sum01+mx3;
}
int main()
{
int n,u,v,w;
scanf("%d",&n);
for(int i=1;i<n;i++) scanf("%d %d %d",&u,&v,&w),g[u].push_back({v,w}),g[v].push_back({u,w});
solve(1);
printf("%d\n",max(dp[1][0],dp[1][2]));
return 0;
}
/*
11
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
11 1 1
8
1 3 49
1 7 52
1 2 38
2 4 25
2 6 21
4 8 2
4 5 5
7
1 2 4
1 3 5
2 4 15
2 5 13
3 6 11
3 7 8
*/
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:30:77: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<n;i++) scanf("%d %d %d",&u,&v,&w),g[u].push_back({v,w}),g[v].push_back({u,w});
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
4992 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
4992 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
7 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
4992 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
7 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
4992 KB |
Output is correct |
23 |
Correct |
10 ms |
5376 KB |
Output is correct |
24 |
Correct |
10 ms |
5376 KB |
Output is correct |
25 |
Correct |
10 ms |
5376 KB |
Output is correct |
26 |
Correct |
13 ms |
5632 KB |
Output is correct |
27 |
Correct |
13 ms |
5760 KB |
Output is correct |
28 |
Correct |
12 ms |
5760 KB |
Output is correct |
29 |
Correct |
12 ms |
5760 KB |
Output is correct |
30 |
Correct |
12 ms |
5760 KB |
Output is correct |
31 |
Correct |
12 ms |
6144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
4992 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
4992 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
4992 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
7 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
4992 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
4992 KB |
Output is correct |
23 |
Correct |
10 ms |
5376 KB |
Output is correct |
24 |
Correct |
10 ms |
5376 KB |
Output is correct |
25 |
Correct |
10 ms |
5376 KB |
Output is correct |
26 |
Correct |
13 ms |
5632 KB |
Output is correct |
27 |
Correct |
13 ms |
5760 KB |
Output is correct |
28 |
Correct |
12 ms |
5760 KB |
Output is correct |
29 |
Correct |
12 ms |
5760 KB |
Output is correct |
30 |
Correct |
12 ms |
5760 KB |
Output is correct |
31 |
Correct |
12 ms |
6144 KB |
Output is correct |
32 |
Correct |
36 ms |
8440 KB |
Output is correct |
33 |
Correct |
37 ms |
8448 KB |
Output is correct |
34 |
Correct |
37 ms |
8440 KB |
Output is correct |
35 |
Correct |
204 ms |
19192 KB |
Output is correct |
36 |
Correct |
195 ms |
19064 KB |
Output is correct |
37 |
Correct |
193 ms |
19192 KB |
Output is correct |
38 |
Correct |
137 ms |
19556 KB |
Output is correct |
39 |
Correct |
139 ms |
19544 KB |
Output is correct |
40 |
Correct |
150 ms |
19424 KB |
Output is correct |
41 |
Correct |
182 ms |
23788 KB |
Output is correct |