#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 = 1e5 + 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 |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7252 KB |
Output is correct |
6 |
Correct |
6 ms |
7252 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7252 KB |
Output is correct |
9 |
Correct |
5 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7372 KB |
Output is correct |
11 |
Correct |
4 ms |
7376 KB |
Output is correct |
12 |
Correct |
6 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7252 KB |
Output is correct |
6 |
Correct |
6 ms |
7252 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7252 KB |
Output is correct |
9 |
Correct |
5 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7372 KB |
Output is correct |
11 |
Correct |
4 ms |
7376 KB |
Output is correct |
12 |
Correct |
6 ms |
7380 KB |
Output is correct |
13 |
Correct |
6 ms |
7380 KB |
Output is correct |
14 |
Correct |
4 ms |
7376 KB |
Output is correct |
15 |
Correct |
5 ms |
7380 KB |
Output is correct |
16 |
Correct |
4 ms |
7380 KB |
Output is correct |
17 |
Correct |
4 ms |
7380 KB |
Output is correct |
18 |
Correct |
4 ms |
7376 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7376 KB |
Output is correct |
21 |
Correct |
4 ms |
7376 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7252 KB |
Output is correct |
6 |
Correct |
6 ms |
7252 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7252 KB |
Output is correct |
9 |
Correct |
5 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7372 KB |
Output is correct |
11 |
Correct |
4 ms |
7376 KB |
Output is correct |
12 |
Correct |
6 ms |
7380 KB |
Output is correct |
13 |
Correct |
6 ms |
7380 KB |
Output is correct |
14 |
Correct |
4 ms |
7376 KB |
Output is correct |
15 |
Correct |
5 ms |
7380 KB |
Output is correct |
16 |
Correct |
4 ms |
7380 KB |
Output is correct |
17 |
Correct |
4 ms |
7380 KB |
Output is correct |
18 |
Correct |
4 ms |
7376 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7376 KB |
Output is correct |
21 |
Correct |
4 ms |
7376 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
10 ms |
8252 KB |
Output is correct |
24 |
Correct |
7 ms |
8148 KB |
Output is correct |
25 |
Correct |
8 ms |
8152 KB |
Output is correct |
26 |
Correct |
12 ms |
9056 KB |
Output is correct |
27 |
Correct |
14 ms |
9036 KB |
Output is correct |
28 |
Correct |
15 ms |
9032 KB |
Output is correct |
29 |
Correct |
17 ms |
9100 KB |
Output is correct |
30 |
Correct |
14 ms |
9044 KB |
Output is correct |
31 |
Correct |
13 ms |
9560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7252 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7252 KB |
Output is correct |
6 |
Correct |
6 ms |
7252 KB |
Output is correct |
7 |
Correct |
4 ms |
7372 KB |
Output is correct |
8 |
Correct |
4 ms |
7252 KB |
Output is correct |
9 |
Correct |
5 ms |
7380 KB |
Output is correct |
10 |
Correct |
5 ms |
7372 KB |
Output is correct |
11 |
Correct |
4 ms |
7376 KB |
Output is correct |
12 |
Correct |
6 ms |
7380 KB |
Output is correct |
13 |
Correct |
6 ms |
7380 KB |
Output is correct |
14 |
Correct |
4 ms |
7376 KB |
Output is correct |
15 |
Correct |
5 ms |
7380 KB |
Output is correct |
16 |
Correct |
4 ms |
7380 KB |
Output is correct |
17 |
Correct |
4 ms |
7380 KB |
Output is correct |
18 |
Correct |
4 ms |
7376 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7376 KB |
Output is correct |
21 |
Correct |
4 ms |
7376 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
10 ms |
8252 KB |
Output is correct |
24 |
Correct |
7 ms |
8148 KB |
Output is correct |
25 |
Correct |
8 ms |
8152 KB |
Output is correct |
26 |
Correct |
12 ms |
9056 KB |
Output is correct |
27 |
Correct |
14 ms |
9036 KB |
Output is correct |
28 |
Correct |
15 ms |
9032 KB |
Output is correct |
29 |
Correct |
17 ms |
9100 KB |
Output is correct |
30 |
Correct |
14 ms |
9044 KB |
Output is correct |
31 |
Correct |
13 ms |
9560 KB |
Output is correct |
32 |
Correct |
57 ms |
16064 KB |
Output is correct |
33 |
Correct |
61 ms |
16200 KB |
Output is correct |
34 |
Correct |
81 ms |
16084 KB |
Output is correct |
35 |
Runtime error |
150 ms |
43832 KB |
Execution killed with signal 11 |
36 |
Halted |
0 ms |
0 KB |
- |