#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "APIO14_beads"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 2e5 + 1;
const ll INF = 1e15;
int n;
ll dp[2][N];
using pi = pair<int, int>;
vector<pi> adj[N];
int tc[2][N];
ll f[2][N], dif[2][N];
ll ans;
void dfs1(int u, int p){
dif[0][u] = dif[1][u] = -INF;
for(auto [w, v]: adj[u]) if(v != p){
dfs1(v, u);
f[0][u] += max(f[0][v], f[1][v] + w);
ll diftmp = (f[0][v] + w) - max(f[0][v], f[1][v] + w);
if(dif[0][u] < diftmp){
dif[1][u] = dif[0][u];
tc[1][u] = tc[0][u];
dif[0][u] = diftmp;
tc[0][u] = v;
} else if(dif[1][u] < diftmp){
dif[1][u] = diftmp;
tc[1][u] = v;
}
}
f[1][u] = f[0][u] + dif[0][u];
// cout << u << " " << f[0][u] << " " << f[1][u] << "\n";
// cout << dif[0][u] << " " << dif[1][u] << "\n\n";
}
void dfs2(int u, int p, ll wei, ll down[2]){
ll tot = f[0][u] + max(down[0], down[1] + wei);
ll diftmp = (down[0] + wei) - max(down[0], down[1] + wei);
ans = max(ans, tot);
// cout << u << " " << down[0] << " " << down[1] << " " << tot << " " << diftmp << "\n";
for(auto [w, v]: adj[u]) if(v != p){
ll dwn[2];
dwn[0] = tot - max(f[0][v], f[1][v] + w);
if(v != tc[0][u]){
dwn[1] = dwn[0] + max(dif[0][u], diftmp);
} else{
dwn[1] = dwn[0] + max(dif[1][u], diftmp);
}
dfs2(v, u, w, dwn);
}
}
int main(){
IOS;
Fi();
cin >> n;
FOR(i, 1, n){
int u, v, w;
cin >> u >> v >> w;
adj[u].eb(w, v);
adj[v].eb(w, u);
}
dfs1(1, -1);
ll down[2] = {0, -INF};
dfs2(1, -1, -INF, down);
cout << ans;
return 0;
}
Compilation message
beads.cpp: In function 'void Fi()':
beads.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen(PROB".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen(PROB".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5020 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5028 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5004 KB |
Output is correct |
6 |
Correct |
3 ms |
5024 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
5040 KB |
Output is correct |
12 |
Correct |
3 ms |
5064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5020 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5028 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5004 KB |
Output is correct |
6 |
Correct |
3 ms |
5024 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
5040 KB |
Output is correct |
12 |
Correct |
3 ms |
5064 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5068 KB |
Output is correct |
16 |
Correct |
4 ms |
5012 KB |
Output is correct |
17 |
Correct |
3 ms |
5028 KB |
Output is correct |
18 |
Correct |
3 ms |
5068 KB |
Output is correct |
19 |
Correct |
3 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5068 KB |
Output is correct |
21 |
Correct |
3 ms |
5068 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5020 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5028 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5004 KB |
Output is correct |
6 |
Correct |
3 ms |
5024 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
5040 KB |
Output is correct |
12 |
Correct |
3 ms |
5064 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5068 KB |
Output is correct |
16 |
Correct |
4 ms |
5012 KB |
Output is correct |
17 |
Correct |
3 ms |
5028 KB |
Output is correct |
18 |
Correct |
3 ms |
5068 KB |
Output is correct |
19 |
Correct |
3 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5068 KB |
Output is correct |
21 |
Correct |
3 ms |
5068 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
23 |
Correct |
5 ms |
5452 KB |
Output is correct |
24 |
Correct |
5 ms |
5420 KB |
Output is correct |
25 |
Correct |
5 ms |
5420 KB |
Output is correct |
26 |
Correct |
6 ms |
5924 KB |
Output is correct |
27 |
Correct |
7 ms |
5840 KB |
Output is correct |
28 |
Correct |
6 ms |
5964 KB |
Output is correct |
29 |
Correct |
6 ms |
5808 KB |
Output is correct |
30 |
Correct |
6 ms |
5944 KB |
Output is correct |
31 |
Correct |
7 ms |
6432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5020 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5028 KB |
Output is correct |
4 |
Correct |
3 ms |
5024 KB |
Output is correct |
5 |
Correct |
3 ms |
5004 KB |
Output is correct |
6 |
Correct |
3 ms |
5024 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
4 ms |
5032 KB |
Output is correct |
11 |
Correct |
3 ms |
5040 KB |
Output is correct |
12 |
Correct |
3 ms |
5064 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5068 KB |
Output is correct |
16 |
Correct |
4 ms |
5012 KB |
Output is correct |
17 |
Correct |
3 ms |
5028 KB |
Output is correct |
18 |
Correct |
3 ms |
5068 KB |
Output is correct |
19 |
Correct |
3 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5068 KB |
Output is correct |
21 |
Correct |
3 ms |
5068 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
23 |
Correct |
5 ms |
5452 KB |
Output is correct |
24 |
Correct |
5 ms |
5420 KB |
Output is correct |
25 |
Correct |
5 ms |
5420 KB |
Output is correct |
26 |
Correct |
6 ms |
5924 KB |
Output is correct |
27 |
Correct |
7 ms |
5840 KB |
Output is correct |
28 |
Correct |
6 ms |
5964 KB |
Output is correct |
29 |
Correct |
6 ms |
5808 KB |
Output is correct |
30 |
Correct |
6 ms |
5944 KB |
Output is correct |
31 |
Correct |
7 ms |
6432 KB |
Output is correct |
32 |
Correct |
27 ms |
9604 KB |
Output is correct |
33 |
Correct |
28 ms |
9508 KB |
Output is correct |
34 |
Correct |
26 ms |
9516 KB |
Output is correct |
35 |
Correct |
183 ms |
23712 KB |
Output is correct |
36 |
Correct |
161 ms |
23824 KB |
Output is correct |
37 |
Correct |
166 ms |
23804 KB |
Output is correct |
38 |
Correct |
106 ms |
24244 KB |
Output is correct |
39 |
Correct |
103 ms |
21112 KB |
Output is correct |
40 |
Correct |
112 ms |
24100 KB |
Output is correct |
41 |
Correct |
156 ms |
29112 KB |
Output is correct |