#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<ll , ll> pll;
const ll maxn = 2e5 + 16 , inf = 2e16;
ll dp[maxn][2] , w[maxn];
vector<pll> adj[maxn];
multiset<ll , greater<ll>> s[maxn];
void dDFS(ll r , ll par){
ll res = 0 , mx;
s[r].insert(-inf);
for(auto p : adj[r]){
ll i = p.first , w = p.second;
if(i == par) continue;
dDFS(i , r);
ll h = max(dp[i][0] , dp[i][1] + w) , o = dp[i][0] + w - h;
res += h;
s[r].insert(o);
}
dp[r][1] = res + *s[r].begin();
dp[r][0] = res;
return;
}
void reroot(ll v , ll u , ll w){
ll h = max(dp[u][0] , dp[u][1] + w) , o = dp[u][0] + w - h;
s[v].erase(s[v].find(o));
dp[v][0] -= h;
dp[v][1] = dp[v][0] + *s[v].begin();
h = max(dp[v][0] , dp[v][1] + w); o = dp[v][0] + w - h;
s[u].insert(o);
dp[u][0] += h;
dp[u][1] = dp[u][0] + *s[u].begin();
return;
}
ll ans = 0;
void rDFS(ll r , ll par){
ans = max(ans , dp[r][0]);
for(auto p : adj[r]){
ll i = p.first , w = p.second;
if(i == par) continue;
reroot(r , i , w);
rDFS(i , r);
reroot(i , r , w);
}
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n;
cin>>n;
for(ll i = 1 ; i < n ; i++){
ll v , u , w;
cin>>v>>u>>w; v--; u--;
adj[v].push_back({u , w}); adj[u].push_back({v , w});
}
dDFS(0 , -1);
rDFS(0 , -1);
cout<<ans<<'\n';
return 0;
}
Compilation message
beads.cpp: In function 'void dDFS(ll, ll)':
beads.cpp:16:15: warning: unused variable 'mx' [-Wunused-variable]
16 | ll res = 0 , mx;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 14 |
Correct |
11 ms |
14420 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14448 KB |
Output is correct |
| 17 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 19 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 20 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 21 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 22 |
Correct |
7 ms |
14420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 14 |
Correct |
11 ms |
14420 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14448 KB |
Output is correct |
| 17 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 19 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 20 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 21 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 22 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 23 |
Correct |
12 ms |
15112 KB |
Output is correct |
| 24 |
Correct |
12 ms |
15232 KB |
Output is correct |
| 25 |
Correct |
12 ms |
15196 KB |
Output is correct |
| 26 |
Correct |
17 ms |
16040 KB |
Output is correct |
| 27 |
Correct |
17 ms |
15956 KB |
Output is correct |
| 28 |
Correct |
24 ms |
15976 KB |
Output is correct |
| 29 |
Correct |
22 ms |
15892 KB |
Output is correct |
| 30 |
Correct |
18 ms |
16012 KB |
Output is correct |
| 31 |
Correct |
18 ms |
16468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 4 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 8 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 10 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 11 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 12 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 13 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 14 |
Correct |
11 ms |
14420 KB |
Output is correct |
| 15 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 16 |
Correct |
8 ms |
14448 KB |
Output is correct |
| 17 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 18 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 19 |
Correct |
8 ms |
14348 KB |
Output is correct |
| 20 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 21 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 22 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 23 |
Correct |
12 ms |
15112 KB |
Output is correct |
| 24 |
Correct |
12 ms |
15232 KB |
Output is correct |
| 25 |
Correct |
12 ms |
15196 KB |
Output is correct |
| 26 |
Correct |
17 ms |
16040 KB |
Output is correct |
| 27 |
Correct |
17 ms |
15956 KB |
Output is correct |
| 28 |
Correct |
24 ms |
15976 KB |
Output is correct |
| 29 |
Correct |
22 ms |
15892 KB |
Output is correct |
| 30 |
Correct |
18 ms |
16012 KB |
Output is correct |
| 31 |
Correct |
18 ms |
16468 KB |
Output is correct |
| 32 |
Correct |
68 ms |
22360 KB |
Output is correct |
| 33 |
Correct |
74 ms |
22460 KB |
Output is correct |
| 34 |
Correct |
71 ms |
22348 KB |
Output is correct |
| 35 |
Correct |
402 ms |
46592 KB |
Output is correct |
| 36 |
Correct |
394 ms |
50100 KB |
Output is correct |
| 37 |
Correct |
399 ms |
50220 KB |
Output is correct |
| 38 |
Correct |
531 ms |
49340 KB |
Output is correct |
| 39 |
Correct |
558 ms |
49216 KB |
Output is correct |
| 40 |
Correct |
448 ms |
49352 KB |
Output is correct |
| 41 |
Correct |
478 ms |
55360 KB |
Output is correct |
