#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 = 1e4 + 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));
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:86:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
888 KB |
Output is correct |
3 |
Correct |
3 ms |
888 KB |
Output is correct |
4 |
Correct |
3 ms |
888 KB |
Output is correct |
5 |
Correct |
3 ms |
888 KB |
Output is correct |
6 |
Correct |
3 ms |
888 KB |
Output is correct |
7 |
Correct |
3 ms |
892 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
888 KB |
Output is correct |
11 |
Correct |
3 ms |
888 KB |
Output is correct |
12 |
Correct |
3 ms |
888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
888 KB |
Output is correct |
3 |
Correct |
3 ms |
888 KB |
Output is correct |
4 |
Correct |
3 ms |
888 KB |
Output is correct |
5 |
Correct |
3 ms |
888 KB |
Output is correct |
6 |
Correct |
3 ms |
888 KB |
Output is correct |
7 |
Correct |
3 ms |
892 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
888 KB |
Output is correct |
11 |
Correct |
3 ms |
888 KB |
Output is correct |
12 |
Correct |
3 ms |
888 KB |
Output is correct |
13 |
Correct |
6 ms |
888 KB |
Output is correct |
14 |
Correct |
5 ms |
956 KB |
Output is correct |
15 |
Correct |
5 ms |
888 KB |
Output is correct |
16 |
Correct |
8 ms |
888 KB |
Output is correct |
17 |
Correct |
7 ms |
888 KB |
Output is correct |
18 |
Correct |
8 ms |
888 KB |
Output is correct |
19 |
Correct |
7 ms |
1016 KB |
Output is correct |
20 |
Correct |
8 ms |
888 KB |
Output is correct |
21 |
Correct |
7 ms |
916 KB |
Output is correct |
22 |
Correct |
8 ms |
1016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
888 KB |
Output is correct |
3 |
Correct |
3 ms |
888 KB |
Output is correct |
4 |
Correct |
3 ms |
888 KB |
Output is correct |
5 |
Correct |
3 ms |
888 KB |
Output is correct |
6 |
Correct |
3 ms |
888 KB |
Output is correct |
7 |
Correct |
3 ms |
892 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
888 KB |
Output is correct |
11 |
Correct |
3 ms |
888 KB |
Output is correct |
12 |
Correct |
3 ms |
888 KB |
Output is correct |
13 |
Correct |
6 ms |
888 KB |
Output is correct |
14 |
Correct |
5 ms |
956 KB |
Output is correct |
15 |
Correct |
5 ms |
888 KB |
Output is correct |
16 |
Correct |
8 ms |
888 KB |
Output is correct |
17 |
Correct |
7 ms |
888 KB |
Output is correct |
18 |
Correct |
8 ms |
888 KB |
Output is correct |
19 |
Correct |
7 ms |
1016 KB |
Output is correct |
20 |
Correct |
8 ms |
888 KB |
Output is correct |
21 |
Correct |
7 ms |
916 KB |
Output is correct |
22 |
Correct |
8 ms |
1016 KB |
Output is correct |
23 |
Correct |
130 ms |
1272 KB |
Output is correct |
24 |
Correct |
125 ms |
1368 KB |
Output is correct |
25 |
Correct |
123 ms |
1272 KB |
Output is correct |
26 |
Correct |
241 ms |
1784 KB |
Output is correct |
27 |
Correct |
242 ms |
1912 KB |
Output is correct |
28 |
Correct |
245 ms |
2548 KB |
Output is correct |
29 |
Correct |
240 ms |
2296 KB |
Output is correct |
30 |
Correct |
242 ms |
2188 KB |
Output is correct |
31 |
Correct |
247 ms |
3132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1016 KB |
Output is correct |
2 |
Correct |
3 ms |
888 KB |
Output is correct |
3 |
Correct |
3 ms |
888 KB |
Output is correct |
4 |
Correct |
3 ms |
888 KB |
Output is correct |
5 |
Correct |
3 ms |
888 KB |
Output is correct |
6 |
Correct |
3 ms |
888 KB |
Output is correct |
7 |
Correct |
3 ms |
892 KB |
Output is correct |
8 |
Correct |
3 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
888 KB |
Output is correct |
11 |
Correct |
3 ms |
888 KB |
Output is correct |
12 |
Correct |
3 ms |
888 KB |
Output is correct |
13 |
Correct |
6 ms |
888 KB |
Output is correct |
14 |
Correct |
5 ms |
956 KB |
Output is correct |
15 |
Correct |
5 ms |
888 KB |
Output is correct |
16 |
Correct |
8 ms |
888 KB |
Output is correct |
17 |
Correct |
7 ms |
888 KB |
Output is correct |
18 |
Correct |
8 ms |
888 KB |
Output is correct |
19 |
Correct |
7 ms |
1016 KB |
Output is correct |
20 |
Correct |
8 ms |
888 KB |
Output is correct |
21 |
Correct |
7 ms |
916 KB |
Output is correct |
22 |
Correct |
8 ms |
1016 KB |
Output is correct |
23 |
Correct |
130 ms |
1272 KB |
Output is correct |
24 |
Correct |
125 ms |
1368 KB |
Output is correct |
25 |
Correct |
123 ms |
1272 KB |
Output is correct |
26 |
Correct |
241 ms |
1784 KB |
Output is correct |
27 |
Correct |
242 ms |
1912 KB |
Output is correct |
28 |
Correct |
245 ms |
2548 KB |
Output is correct |
29 |
Correct |
240 ms |
2296 KB |
Output is correct |
30 |
Correct |
242 ms |
2188 KB |
Output is correct |
31 |
Correct |
247 ms |
3132 KB |
Output is correct |
32 |
Runtime error |
3 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
33 |
Halted |
0 ms |
0 KB |
- |