#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 int 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;
}
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});
}
ll ans = 0;
for(int i = 1; i <= n; i++){
memset(dp1, 0, sizeof dp1);
memset(dp2, 0, sizeof dp2);
DFS(i, -1);
ans = max(ans, dp1[i]);
}
cout << ans;
return 0;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
Compilation message
beads.cpp:23:16: warning: overflow in implicit constant conversion [-Woverflow]
const ll Inf = 2242545357980376863LL;
^~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'll DFS(ll, ll)':
beads.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
632 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Correct |
3 ms |
636 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
632 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Correct |
3 ms |
636 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
3 ms |
636 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
3 ms |
632 KB |
Output is correct |
16 |
Correct |
4 ms |
632 KB |
Output is correct |
17 |
Correct |
11 ms |
636 KB |
Output is correct |
18 |
Correct |
4 ms |
632 KB |
Output is correct |
19 |
Correct |
4 ms |
632 KB |
Output is correct |
20 |
Correct |
4 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
632 KB |
Output is correct |
22 |
Correct |
4 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
632 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Correct |
3 ms |
636 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
3 ms |
636 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
3 ms |
632 KB |
Output is correct |
16 |
Correct |
4 ms |
632 KB |
Output is correct |
17 |
Correct |
11 ms |
636 KB |
Output is correct |
18 |
Correct |
4 ms |
632 KB |
Output is correct |
19 |
Correct |
4 ms |
632 KB |
Output is correct |
20 |
Correct |
4 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
632 KB |
Output is correct |
22 |
Correct |
4 ms |
632 KB |
Output is correct |
23 |
Correct |
777 ms |
988 KB |
Output is correct |
24 |
Correct |
811 ms |
888 KB |
Output is correct |
25 |
Correct |
916 ms |
1016 KB |
Output is correct |
26 |
Execution timed out |
1083 ms |
1144 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
2 ms |
632 KB |
Output is correct |
4 |
Correct |
2 ms |
632 KB |
Output is correct |
5 |
Correct |
3 ms |
632 KB |
Output is correct |
6 |
Correct |
2 ms |
632 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
8 |
Correct |
3 ms |
636 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
5 ms |
632 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
3 ms |
636 KB |
Output is correct |
14 |
Correct |
3 ms |
632 KB |
Output is correct |
15 |
Correct |
3 ms |
632 KB |
Output is correct |
16 |
Correct |
4 ms |
632 KB |
Output is correct |
17 |
Correct |
11 ms |
636 KB |
Output is correct |
18 |
Correct |
4 ms |
632 KB |
Output is correct |
19 |
Correct |
4 ms |
632 KB |
Output is correct |
20 |
Correct |
4 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
632 KB |
Output is correct |
22 |
Correct |
4 ms |
632 KB |
Output is correct |
23 |
Correct |
777 ms |
988 KB |
Output is correct |
24 |
Correct |
811 ms |
888 KB |
Output is correct |
25 |
Correct |
916 ms |
1016 KB |
Output is correct |
26 |
Execution timed out |
1083 ms |
1144 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |