#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f = stdin;
FILE *g = stdout;
struct edge_t{
int to,cost;
edge_t(){
to = cost = 0;
}
edge_t(int to,int cost){
this->to = to;
this->cost = cost;
}
};
const int NMAX = 2e5;
int n;
vector<edge_t> graph[NMAX + 5];
int dp[NMAX + 5][2];
int best_nodes[NMAX + 5][2];
int best_cost[NMAX + 5][2];
int ans;
void dfs1(int nod,int tata,int cost_tata){
dp[nod][0] = dp[nod][1] = 0;
best_nodes[nod][0] = best_nodes[nod][1] = 0;
int best_upgrade_cost = -(1 << 30);
int best_upgrade_cost2 = -(1 << 30);
for(auto it:graph[nod]){
if(it.to == tata){
continue;
}
dfs1(it.to,nod,it.cost);
dp[nod][0] += max(dp[it.to][0],dp[it.to][1]);
int it_cost_to_upgrade = dp[it.to][0] - max(dp[it.to][0],dp[it.to][1]) + it.cost;
if(it_cost_to_upgrade > best_upgrade_cost){
best_upgrade_cost2 = best_upgrade_cost;
best_nodes[nod][1] = best_nodes[nod][0];
best_upgrade_cost = it_cost_to_upgrade;
best_nodes[nod][0]= it.to;
}
else if(it_cost_to_upgrade > best_upgrade_cost2){
best_upgrade_cost2 = it_cost_to_upgrade;
best_nodes[nod][1]= it.to;
}
}
best_cost[nod][0] = best_upgrade_cost;
best_cost[nod][1] = best_upgrade_cost2;
if(tata){
if(best_upgrade_cost == -(1 << 30)){
dp[nod][1] = -(1 << 30);
}
else{
dp[nod][1] = dp[nod][0] + best_upgrade_cost + cost_tata;
}
}
else{
if(best_upgrade_cost2 == -(1 << 30)){
dp[nod][1] = -(1 << 30);
}
else{
dp[nod][1] = dp[nod][0] + best_upgrade_cost + best_upgrade_cost2;
}
}
}
void dfs2(int nod,int tata){
ans = max(ans,dp[nod][0]);
ans = max(ans,dp[nod][1]);
int back_son[2];
int back[2] = {dp[nod][0],dp[nod][1]};
for(auto it:graph[nod]){
if(it.to == tata){
continue;
}
back_son[0] = dp[it.to][0];
back_son[1] = dp[it.to][1];
dp[nod][0] -= max(dp[it.to][0],dp[it.to][1]);
if(it.to == best_nodes[nod][0] || it.to == best_nodes[nod][1]){
if(best_cost[nod][1] != -(1 << 30)){
dp[nod][1] -= dp[it.to][0];
}
else{
dp[nod][1] = -(1 << 30);
}
}
else{
if(best_cost[nod][1] == -(1 << 30)){
dp[nod][1] = -(1 << 30);
}
else{
dp[nod][1] = dp[nod][1] - max(dp[it.to][0],dp[it.to][1]) - best_cost[nod][1] + it.cost;
}
}
dp[it.to][0] += max(dp[nod][0],dp[nod][1]);
int nod_cost = dp[nod][0] - max(dp[nod][0],dp[nod][1]) + it.cost;
if(best_cost[it.to][0] < nod_cost){
best_cost[it.to][1] = best_cost[it.to][0];
best_nodes[it.to][1] = best_nodes[it.to][0];
best_cost[it.to][0] = nod_cost;
best_nodes[it.to][0] = nod;
}
else if(best_cost[it.to][1] < nod_cost){
best_cost[it.to][1] = nod_cost;
best_nodes[it.to][1] = nod;
}
if(best_cost[it.to][1] == -(1 << 30)){
dp[it.to][1] = -(1 << 30);
}
else{
dp[it.to][1] = dp[it.to][0] + best_cost[it.to][0] + best_cost[it.to][1];
}
dfs2(it.to,nod);
dp[it.to][0] = back_son[0];
dp[it.to][1] = back_son[1];
dp[nod][0] = back[0];
dp[nod][1] = back[1];
}
}
int main(){
fscanf(f,"%d",&n);
for(int i = 1;i < n;i++){
int a,b,c;
fscanf(f,"%d %d %d",&a,&b,&c);
graph[a].push_back(edge_t(b,c));
graph[b].push_back(edge_t(a,c));
}
dfs1(1,0,0);
dfs2(1,0);
fprintf(g,"%d",ans);
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:148:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(f,"%d",&n);
~~~~~~^~~~~~~~~~~
beads.cpp:152:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(f,"%d %d %d",&a,&b,&c);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
5120 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
5 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
5 ms |
4992 KB |
Output is correct |
21 |
Correct |
5 ms |
4992 KB |
Output is correct |
22 |
Correct |
5 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
5120 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
5 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
5 ms |
4992 KB |
Output is correct |
21 |
Correct |
5 ms |
4992 KB |
Output is correct |
22 |
Correct |
5 ms |
4992 KB |
Output is correct |
23 |
Correct |
8 ms |
5376 KB |
Output is correct |
24 |
Correct |
8 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
12 ms |
5632 KB |
Output is correct |
27 |
Correct |
11 ms |
5632 KB |
Output is correct |
28 |
Correct |
10 ms |
5680 KB |
Output is correct |
29 |
Correct |
11 ms |
5632 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
11 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
5 ms |
4992 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
5120 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
5 ms |
4992 KB |
Output is correct |
16 |
Correct |
5 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
5 ms |
4992 KB |
Output is correct |
20 |
Correct |
5 ms |
4992 KB |
Output is correct |
21 |
Correct |
5 ms |
4992 KB |
Output is correct |
22 |
Correct |
5 ms |
4992 KB |
Output is correct |
23 |
Correct |
8 ms |
5376 KB |
Output is correct |
24 |
Correct |
8 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
12 ms |
5632 KB |
Output is correct |
27 |
Correct |
11 ms |
5632 KB |
Output is correct |
28 |
Correct |
10 ms |
5680 KB |
Output is correct |
29 |
Correct |
11 ms |
5632 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
11 ms |
6016 KB |
Output is correct |
32 |
Correct |
39 ms |
8056 KB |
Output is correct |
33 |
Correct |
41 ms |
8052 KB |
Output is correct |
34 |
Correct |
44 ms |
8104 KB |
Output is correct |
35 |
Correct |
267 ms |
17144 KB |
Output is correct |
36 |
Correct |
258 ms |
17760 KB |
Output is correct |
37 |
Correct |
255 ms |
17760 KB |
Output is correct |
38 |
Correct |
183 ms |
18020 KB |
Output is correct |
39 |
Correct |
182 ms |
18004 KB |
Output is correct |
40 |
Correct |
221 ms |
17868 KB |
Output is correct |
41 |
Correct |
260 ms |
21572 KB |
Output is correct |