#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
const int MAXN = 2e5+10 ;
const int inf = 1e9+7 ;
using namespace std ;
int n ;
int ans ;
int dp[MAXN][2] ;
vector< pair<int,int> > adj[MAXN] ;
void dfs(int x, int father )
{
int edgeFather = -inf ;
vector< pair<int,int> > children ;
for(auto e : adj[x] )
{
if(e.first == father)
edgeFather = e.second ;
else
{
dfs(e.first, x) ;
children.push_back(e) ;
}
}
dp[x][0] = 0;
dp[x][1] = edgeFather ;
int maxCte = -inf ;
for(auto e : children )
{
int pos1 = dp[e.first][1] ;
int pos2 = dp[e.first][0] ;
dp[x][0] += max(pos1, pos2) ;
dp[x][1] += max(pos1,pos2) ;
maxCte = max(maxCte, -max(pos1,pos2) + e.second + pos2 ) ;
}
dp[x][1] += maxCte ;
}
void dfsSpin(int x, int father)
{
vector< pair<int,int> > children ;
for(auto e : adj[x] )
children.push_back(e) ;
int m = sz(children) ;
int soma = 0 ;
vector<int> pref(m) , suf(m) ;
for(int i = 0 , ii = m-1 ; i < m ; i++ , ii-- )
{
int vert = children[i].first ;
int edge = children[i].second ;
soma += max( dp[vert][0] , dp[vert][1] ) ;
pref[i] = -max(dp[vert][0] , dp[vert][1]) + edge + dp[vert][0] ;
vert = children[ii].first ;
edge = children[ii].second ;
suf[ii] = -max(dp[vert][0] , dp[vert][1]) + edge + dp[vert][0] ;
if(!i) continue ;
pref[i] = max(pref[i-1], pref[i]) ;
suf[ii] = max(suf[ii+1] , suf[ii]) ;
}
ans = max(ans, soma ) ;
for(int i = 0 ; i < m ; i++ )
{
int vert = children[i].first ;
int edge = children[i].second ;
if(vert == father) continue ;
int save0 = dp[vert][0] ;
int save1 = dp[vert][1] ;
int cte = -inf ;
if(i) cte = max(cte, pref[i-1]) ;
if(i+1 < m) cte = max(cte, suf[i+1]) ;
dp[x][0] = soma-max(save0,save1) ;
dp[x][1] = soma-max(save0,save1) + cte + edge ;
dfsSpin(vert, x) ;
dp[vert][0] = save0 ;
dp[vert][1] = save1 ;
}
}
int main()
{
scanf("%d", &n ) ;
if(n == 1)
{
printf("0\n") ;
return 0 ;
}
for(int i = 1 , a , b , c ; i < n ; i++ )
{
scanf("%d%d%d", &a, &b, &c ) ;
adj[a].push_back(make_pair(b,c)) ;
adj[b].push_back( make_pair(a,c) ) ;
}
dfs(1,-1);
dfsSpin(1,-1) ;
printf("%d\n" , ans ) ;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d", &n ) ;
| ~~~~~^~~~~~~~~~~
beads.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%d%d%d", &a, &b, &c ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
3 ms |
4972 KB |
Output is correct |
4 |
Correct |
3 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
8 |
Correct |
3 ms |
4972 KB |
Output is correct |
9 |
Correct |
4 ms |
4972 KB |
Output is correct |
10 |
Correct |
3 ms |
4972 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
4 ms |
4972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
3 ms |
4972 KB |
Output is correct |
4 |
Correct |
3 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
8 |
Correct |
3 ms |
4972 KB |
Output is correct |
9 |
Correct |
4 ms |
4972 KB |
Output is correct |
10 |
Correct |
3 ms |
4972 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
4 ms |
4972 KB |
Output is correct |
13 |
Correct |
3 ms |
4972 KB |
Output is correct |
14 |
Correct |
3 ms |
4972 KB |
Output is correct |
15 |
Correct |
4 ms |
4972 KB |
Output is correct |
16 |
Correct |
4 ms |
4972 KB |
Output is correct |
17 |
Correct |
4 ms |
4972 KB |
Output is correct |
18 |
Correct |
4 ms |
4992 KB |
Output is correct |
19 |
Correct |
4 ms |
5100 KB |
Output is correct |
20 |
Correct |
4 ms |
5100 KB |
Output is correct |
21 |
Correct |
4 ms |
4972 KB |
Output is correct |
22 |
Correct |
4 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
3 ms |
4972 KB |
Output is correct |
4 |
Correct |
3 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
8 |
Correct |
3 ms |
4972 KB |
Output is correct |
9 |
Correct |
4 ms |
4972 KB |
Output is correct |
10 |
Correct |
3 ms |
4972 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
4 ms |
4972 KB |
Output is correct |
13 |
Correct |
3 ms |
4972 KB |
Output is correct |
14 |
Correct |
3 ms |
4972 KB |
Output is correct |
15 |
Correct |
4 ms |
4972 KB |
Output is correct |
16 |
Correct |
4 ms |
4972 KB |
Output is correct |
17 |
Correct |
4 ms |
4972 KB |
Output is correct |
18 |
Correct |
4 ms |
4992 KB |
Output is correct |
19 |
Correct |
4 ms |
5100 KB |
Output is correct |
20 |
Correct |
4 ms |
5100 KB |
Output is correct |
21 |
Correct |
4 ms |
4972 KB |
Output is correct |
22 |
Correct |
4 ms |
5100 KB |
Output is correct |
23 |
Correct |
7 ms |
5484 KB |
Output is correct |
24 |
Correct |
7 ms |
5356 KB |
Output is correct |
25 |
Correct |
7 ms |
5356 KB |
Output is correct |
26 |
Correct |
13 ms |
5612 KB |
Output is correct |
27 |
Correct |
11 ms |
5612 KB |
Output is correct |
28 |
Correct |
9 ms |
5868 KB |
Output is correct |
29 |
Correct |
9 ms |
5740 KB |
Output is correct |
30 |
Correct |
9 ms |
5740 KB |
Output is correct |
31 |
Correct |
11 ms |
6636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4972 KB |
Output is correct |
2 |
Correct |
4 ms |
4972 KB |
Output is correct |
3 |
Correct |
3 ms |
4972 KB |
Output is correct |
4 |
Correct |
3 ms |
4972 KB |
Output is correct |
5 |
Correct |
4 ms |
4972 KB |
Output is correct |
6 |
Correct |
4 ms |
4972 KB |
Output is correct |
7 |
Correct |
4 ms |
4972 KB |
Output is correct |
8 |
Correct |
3 ms |
4972 KB |
Output is correct |
9 |
Correct |
4 ms |
4972 KB |
Output is correct |
10 |
Correct |
3 ms |
4972 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
4 ms |
4972 KB |
Output is correct |
13 |
Correct |
3 ms |
4972 KB |
Output is correct |
14 |
Correct |
3 ms |
4972 KB |
Output is correct |
15 |
Correct |
4 ms |
4972 KB |
Output is correct |
16 |
Correct |
4 ms |
4972 KB |
Output is correct |
17 |
Correct |
4 ms |
4972 KB |
Output is correct |
18 |
Correct |
4 ms |
4992 KB |
Output is correct |
19 |
Correct |
4 ms |
5100 KB |
Output is correct |
20 |
Correct |
4 ms |
5100 KB |
Output is correct |
21 |
Correct |
4 ms |
4972 KB |
Output is correct |
22 |
Correct |
4 ms |
5100 KB |
Output is correct |
23 |
Correct |
7 ms |
5484 KB |
Output is correct |
24 |
Correct |
7 ms |
5356 KB |
Output is correct |
25 |
Correct |
7 ms |
5356 KB |
Output is correct |
26 |
Correct |
13 ms |
5612 KB |
Output is correct |
27 |
Correct |
11 ms |
5612 KB |
Output is correct |
28 |
Correct |
9 ms |
5868 KB |
Output is correct |
29 |
Correct |
9 ms |
5740 KB |
Output is correct |
30 |
Correct |
9 ms |
5740 KB |
Output is correct |
31 |
Correct |
11 ms |
6636 KB |
Output is correct |
32 |
Correct |
44 ms |
8044 KB |
Output is correct |
33 |
Correct |
43 ms |
8044 KB |
Output is correct |
34 |
Correct |
42 ms |
8044 KB |
Output is correct |
35 |
Correct |
281 ms |
17644 KB |
Output is correct |
36 |
Correct |
267 ms |
17644 KB |
Output is correct |
37 |
Correct |
280 ms |
17644 KB |
Output is correct |
38 |
Correct |
182 ms |
21600 KB |
Output is correct |
39 |
Correct |
160 ms |
21348 KB |
Output is correct |
40 |
Correct |
179 ms |
20824 KB |
Output is correct |
41 |
Correct |
264 ms |
29928 KB |
Output is correct |