#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<pll, pll> node;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll Mod = 1000000007LL;
const int Maxn = 2e5 + 10;
const int Maxk = 60;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
vector<pll> G[Maxn];
ll dp1[Maxn], dp2[Maxn];
ll DFS(ll u, ll p){
ll adj;
ll mx = -Inf;
for(auto ed : G[u]){
adj = ed.F;
if(adj == p) continue;
DFS(adj, u);
dp1[u] += max(dp1[adj], dp2[adj] + ed.S);
mx = max(mx, ed.S + dp1[adj] - max(dp1[adj], dp2[adj] + ed.S));
}
dp2[u] = dp1[u] + mx;
}
ll dpu1[Maxn], dpu2[Maxn];
ll pssm[Maxn], psmx[Maxn];
ll sfsm[Maxn], sfmx[Maxn];
ll ans = 0;
ll dfs(ll u, ll p, ll w){
vector< pair<pll, pll> > S;
ll adj;
for(auto ed : G[u]){
adj = ed.F;
if(adj == p){
S.pb({{dpu1[u], dpu2[u]}, {w, adj}});
} else {
S.pb({{dp1[adj], dp2[adj]}, {ed.S, adj}});
}
}
ll N = S.size();
pssm[0] = 0;
for(int i = 1; i <= N; i++) pssm[i] = pssm[i - 1] + max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F);
psmx[0] = -Inf;
for(int i = 1; i <= N; i++) psmx[i] = max(psmx[i - 1] , S[i - 1].F.F + S[i - 1].S.F - max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F) );
reverse(all(S));
for(int i = 0; i <= N; i++) sfsm[i] = pssm[i];
for(int i = 0; i <= N; i++) sfmx[i] = psmx[i];
//swap(pssm, sfsm);
//swap(psmx, sfmx);
pssm[0] = 0;
for(int i = 1; i <= N; i++) pssm[i] = pssm[i - 1] + max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F);
psmx[0] = -Inf;
for(int i = 1; i <= N; i++) psmx[i] = max(psmx[i - 1] , S[i - 1].F.F + S[i - 1].S.F - max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F) );
//if(u == 3) cerr <<
ans = max(pssm[N], ans);
for(int i = 0; i < N; i++){
adj = S[i].S.S;
if(adj == p) continue;
dpu1[adj] = pssm[i] + sfsm[N - 1 - i];
dpu2[adj] = dpu1[adj] + max(psmx[i], sfmx[N - 1 - i]);
}
for(auto ed : G[u]){
adj = ed.F;
if(adj != p) dfs(adj, u, ed.S);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n;
cin >> n;
ll u, v, w;
for(int i = 1; i < n; i++){
cin >> u >> v >> w;
G[u].pb({v, w});
G[v].pb({u, w});
}
DFS(1, -1);
dfs(1, -1, 0);
cout << ans;
return 0;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
Compilation message
beads.cpp: In function 'll DFS(ll, ll)':
beads.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
beads.cpp: In function 'll dfs(ll, ll, ll)':
beads.cpp:88:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5116 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5116 KB |
Output is correct |
4 |
Correct |
7 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5084 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
5112 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5116 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5116 KB |
Output is correct |
4 |
Correct |
7 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5084 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
5112 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
6 ms |
5112 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
13 ms |
5240 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
7 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5116 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5116 KB |
Output is correct |
4 |
Correct |
7 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5084 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
5112 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
6 ms |
5112 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
13 ms |
5240 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
7 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
10 ms |
5496 KB |
Output is correct |
24 |
Correct |
10 ms |
5496 KB |
Output is correct |
25 |
Correct |
11 ms |
5496 KB |
Output is correct |
26 |
Correct |
14 ms |
5880 KB |
Output is correct |
27 |
Correct |
14 ms |
5880 KB |
Output is correct |
28 |
Correct |
14 ms |
6636 KB |
Output is correct |
29 |
Correct |
13 ms |
6392 KB |
Output is correct |
30 |
Correct |
14 ms |
6284 KB |
Output is correct |
31 |
Correct |
15 ms |
7292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5116 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5116 KB |
Output is correct |
4 |
Correct |
7 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
6 ms |
5084 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
5112 KB |
Output is correct |
11 |
Correct |
6 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
6 ms |
5112 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
13 ms |
5240 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
7 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
10 ms |
5496 KB |
Output is correct |
24 |
Correct |
10 ms |
5496 KB |
Output is correct |
25 |
Correct |
11 ms |
5496 KB |
Output is correct |
26 |
Correct |
14 ms |
5880 KB |
Output is correct |
27 |
Correct |
14 ms |
5880 KB |
Output is correct |
28 |
Correct |
14 ms |
6636 KB |
Output is correct |
29 |
Correct |
13 ms |
6392 KB |
Output is correct |
30 |
Correct |
14 ms |
6284 KB |
Output is correct |
31 |
Correct |
15 ms |
7292 KB |
Output is correct |
32 |
Correct |
55 ms |
9932 KB |
Output is correct |
33 |
Correct |
57 ms |
9988 KB |
Output is correct |
34 |
Correct |
46 ms |
9976 KB |
Output is correct |
35 |
Correct |
300 ms |
25248 KB |
Output is correct |
36 |
Correct |
328 ms |
25300 KB |
Output is correct |
37 |
Correct |
337 ms |
25208 KB |
Output is correct |
38 |
Correct |
233 ms |
35908 KB |
Output is correct |
39 |
Correct |
241 ms |
33972 KB |
Output is correct |
40 |
Correct |
272 ms |
33096 KB |
Output is correct |
41 |
Correct |
343 ms |
40752 KB |
Output is correct |