#include <stdio.h>
#include <algorithm>
#include <vector>
#define N_MAX 200000
#define INF 0x7fffffff
using namespace std;
struct rope {
int next;
int cost;
};
vector <rope> Rope[N_MAX+1];
int N, Check[N_MAX+1], D1[N_MAX+1], D2[N_MAX+1], D3[N_MAX+1], D4[N_MAX+1], D5[N_MAX+1];
void input(void) {
int i, in1, in2, in3;
scanf("%d",&N);
for(i=1 ; i<N ; i++) {
scanf("%d %d %d",&in1,&in2,&in3);
Rope[in1].push_back({in2,in3});
Rope[in2].push_back({in1,in3});
}
}
void treeDP(int now) {
int i, j=Rope[now].size();
int anc=-1, temp, max1, max2, max3, max4, max5, j1=-1, j2=-1;
for(i=0 ; i<j ; i++) {
if(Check[Rope[now][i].next])
anc=i;
else {
Check[Rope[now][i].next]=1;
treeDP(Rope[now][i].next);
}
}
if(anc>=0)
D1[now]=D4[now]=Rope[now][anc].cost;
max1=max2=max3=max4=max5=-INF;
for(i=0 ; i<j ; i++) {
if(i!=anc) {
temp=max(D4[Rope[now][i].next],D5[Rope[now][i].next]);
D1[now]+=temp;
D2[now]+=temp;
D3[now]+=temp;
D4[now]+=temp;
D5[now]+=temp;
if(max1<Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp) {
max3=max1;
max1=Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp;
j1=i;
}
else if(max3<Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp)
max3=Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp;
if(max2<Rope[now][i].cost+D5[Rope[now][i].next]-temp) {
max4=max2;
max2=Rope[now][i].cost+D5[Rope[now][i].next]-temp;
j2=i;
}
else if(max4<Rope[now][i].cost+D5[Rope[now][i].next]-temp)
max4=Rope[now][i].cost+D5[Rope[now][i].next]-temp;
if(max5<max(D1[Rope[now][i].next],max(D2[Rope[now][i].next],D3[Rope[now][i].next]))-temp)
max5=max(D1[Rope[now][i].next],max(D2[Rope[now][i].next],D3[Rope[now][i].next]))-temp;
}
}
if(anc==-1 || j<=1)
D1[now]=0;
else
D1[now]+=max1;
if((anc==-1 && j<=1) || (anc>=0 && j<=2))
D2[now]=0;
else {
if(j1==j2)
D2[now]+=max(max1+max4,max2+max3);
else
D2[now]+=max1+max2;
}
if((anc==-1 && j==0) || (anc>=0 && j<=1))
D3[now]=0;
else
D3[now]+=max5;
if(anc==-1 || j<=1)
D4[now]=0;
else
D4[now]+=max2;
}
int main(void) {
input();
Check[1]=1;
treeDP(1);
printf("%d",max(D2[1],D3[1]));
return 0;
}
Compilation message
beads.cpp: In function 'void input()':
beads.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
beads.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&in1,&in2,&in3);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
5120 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 |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
5 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
5120 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 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 |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
5120 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 |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
5 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
5120 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
5 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 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 |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
5120 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 |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
5 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
5120 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
5 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 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 |
7 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
11 ms |
5632 KB |
Output is correct |
27 |
Correct |
11 ms |
5632 KB |
Output is correct |
28 |
Correct |
10 ms |
5760 KB |
Output is correct |
29 |
Correct |
10 ms |
5632 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
11 ms |
6144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Correct |
5 ms |
5120 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 |
5120 KB |
Output is correct |
7 |
Correct |
6 ms |
5120 KB |
Output is correct |
8 |
Correct |
5 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
5120 KB |
Output is correct |
10 |
Correct |
6 ms |
5120 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
5 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5120 KB |
Output is correct |
17 |
Correct |
6 ms |
5120 KB |
Output is correct |
18 |
Correct |
6 ms |
5120 KB |
Output is correct |
19 |
Correct |
5 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
5120 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 |
7 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
11 ms |
5632 KB |
Output is correct |
27 |
Correct |
11 ms |
5632 KB |
Output is correct |
28 |
Correct |
10 ms |
5760 KB |
Output is correct |
29 |
Correct |
10 ms |
5632 KB |
Output is correct |
30 |
Correct |
10 ms |
5632 KB |
Output is correct |
31 |
Correct |
11 ms |
6144 KB |
Output is correct |
32 |
Correct |
40 ms |
8056 KB |
Output is correct |
33 |
Correct |
35 ms |
8056 KB |
Output is correct |
34 |
Correct |
35 ms |
8064 KB |
Output is correct |
35 |
Correct |
214 ms |
17144 KB |
Output is correct |
36 |
Correct |
236 ms |
17340 KB |
Output is correct |
37 |
Correct |
221 ms |
17144 KB |
Output is correct |
38 |
Correct |
159 ms |
17512 KB |
Output is correct |
39 |
Correct |
151 ms |
16736 KB |
Output is correct |
40 |
Correct |
182 ms |
17400 KB |
Output is correct |
41 |
Correct |
222 ms |
22556 KB |
Output is correct |