#include<stdio.h>
#include<math.h>
#include<vector>
#define LL long long
#define MAX_N 200005
#define inf 1000000000000000
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
struct emp{
LL y,cost;
};
LL n;
LL master[MAX_N],mid_master[MAX_N],branch[MAX_N],mid_branch[MAX_N];
vector<emp> net[MAX_N];
LL max_cost[4];
emp max_branch[4],max_master[4];
void make_branch(LL x,LL pa,LL cost){
LL i,sz;
LL maxx=0,y,z=0;
sz=net[x].size();
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
maxx+=mid_branch[net[x][i].y];
}
maxx=MAX(maxx,branch[x]);
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
y=cost+net[x][i].cost+branch[x]-mid_branch[net[x][i].y]+branch[net[x][i].y];
//printf("%lld %lld %lld %lld\n",pa,x,net[x][i].y,y);
maxx=MAX(maxx,y);
}
mid_branch[x]=MAX(mid_branch[x],maxx);
branch[pa]+=mid_branch[x];
}
void make_master(LL x,LL pa,LL cost){
LL i,y,sz;
sz=net[x].size();
mid_master[x]=MAX(mid_master[x],master[x]);
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
y=master[net[x][i].y]+cost+net[x][i].cost+branch[x]-mid_branch[net[x][i].y];
mid_master[x]=MAX(mid_master[x],y);
}
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
y=branch[x]-mid_branch[net[x][i].y]+master[net[x][i].y];
master[x]=MAX(master[x],y);
y=mid_master[net[x][i].y]+branch[x]-mid_branch[net[x][i].y];
master[x]=MAX(master[x],y);
}
}
void merge(LL x,LL pa,LL cost){
LL i,sz;
LL y,z;
max_cost[0]=max_cost[1]=-inf;
sz=net[x].size();
if(pa && sz<3) return;
if(!pa && sz<2) return;
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
y=-mid_branch[net[x][i].y]+net[x][i].cost+branch[net[x][i].y];
if(max_cost[0]<y){
max_cost[1]=max_cost[0];
max_cost[0]=y;
}else if(max_cost[1]<y){
max_cost[1]=y;
}
}
master[x]=MAX(master[x],branch[x]+max_cost[0]+max_cost[1]);
max_branch[0].cost=max_branch[1].cost=-inf;
max_branch[0].y=max_branch[1].y=-1;
max_master[0].cost=max_master[1].cost=-inf;
max_master[0].y=max_master[1].y=-1;
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
y=-mid_branch[net[x][i].y]+branch[net[x][i].y]+net[x][i].cost;
if(y>max_branch[0].cost){
max_branch[1]=max_branch[0];
max_branch[0].cost=y;
max_branch[0].y=net[x][i].y;
}else if(y>max_branch[1].cost){
max_branch[1].cost=y;
max_branch[1].y=net[x][i].y;
}
}
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
y=-mid_branch[net[x][i].y]+master[net[x][i].y]+net[x][i].cost;
if(y>max_master[0].cost){
max_master[1]=max_master[0];
max_master[0].cost=y;
max_master[0].y=net[x][i].y;
}else if(y>max_master[1].cost){
max_master[1].cost=y;
max_master[1].y=net[x][i].y;
}
}
//printf("%lld : %lld %lld : %lld %lld\n",x,max_branch[0].y,max_branch[1].y,max_master[0].y,max_branch[1].y);
if(max_master[0].y-max_branch[0].y){
master[x]=MAX(master[x],max_master[0].cost+max_branch[0].cost+branch[x]);
}else{
master[x]=MAX(master[x],MAX(max_master[0].cost+max_branch[1].cost,max_master[1].cost+max_branch[0].cost)+branch[x]);
}
}
void make_ans(LL x,LL pa,LL cost){
LL i,sz,y;
sz=net[x].size();
for(i=0;i<sz;i++){
if(net[x][i].y==pa) continue;
make_ans(net[x][i].y,x,net[x][i].cost);
}
make_branch(x,pa,cost);
merge(x,pa,cost);
make_master(x,pa,cost);
master[pa]=MAX(master[pa],master[x]);
//printf("%lld : %lld %lld %lld\n",x,master[x],branch[x],mid_branch[x]);
}
int main(){
LL i,x,y,cost;
emp node;
scanf("%lld",&n);
for(i=1;i<n;i++){
scanf("%lld %lld %lld",&x,&y,&cost);
node.y=y;
node.cost=cost;
net[x].push_back(node);
node.y=x;
net[y].push_back(node);
}
make_ans(1,0,0);
printf("%lld\n",MAX(master[1],branch[1]));
return 0;
}
Compilation message
beads.cpp: In function 'void make_branch(long long int, long long int, long long int)':
beads.cpp:19:14: warning: unused variable 'z' [-Wunused-variable]
LL maxx=0,y,z=0;
^
beads.cpp: In function 'void merge(long long int, long long int, long long int)':
beads.cpp:54:7: warning: unused variable 'z' [-Wunused-variable]
LL y,z;
^
beads.cpp: In function 'void make_ans(long long int, long long int, long long int)':
beads.cpp:107:10: warning: unused variable 'y' [-Wunused-variable]
LL i,sz,y;
^
beads.cpp: In function 'int main()':
beads.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
beads.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&x,&y,&cost);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
4964 KB |
Output is correct |
15 |
Correct |
5 ms |
5120 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 |
4992 KB |
Output is correct |
20 |
Correct |
5 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 |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
4964 KB |
Output is correct |
15 |
Correct |
5 ms |
5120 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 |
4992 KB |
Output is correct |
20 |
Correct |
5 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 |
9 ms |
5376 KB |
Output is correct |
24 |
Correct |
8 ms |
5504 KB |
Output is correct |
25 |
Correct |
8 ms |
5504 KB |
Output is correct |
26 |
Correct |
12 ms |
5888 KB |
Output is correct |
27 |
Correct |
12 ms |
5888 KB |
Output is correct |
28 |
Correct |
10 ms |
5756 KB |
Output is correct |
29 |
Correct |
10 ms |
5760 KB |
Output is correct |
30 |
Correct |
11 ms |
5888 KB |
Output is correct |
31 |
Correct |
11 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
5120 KB |
Output is correct |
13 |
Correct |
6 ms |
5120 KB |
Output is correct |
14 |
Correct |
6 ms |
4964 KB |
Output is correct |
15 |
Correct |
5 ms |
5120 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 |
4992 KB |
Output is correct |
20 |
Correct |
5 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 |
9 ms |
5376 KB |
Output is correct |
24 |
Correct |
8 ms |
5504 KB |
Output is correct |
25 |
Correct |
8 ms |
5504 KB |
Output is correct |
26 |
Correct |
12 ms |
5888 KB |
Output is correct |
27 |
Correct |
12 ms |
5888 KB |
Output is correct |
28 |
Correct |
10 ms |
5756 KB |
Output is correct |
29 |
Correct |
10 ms |
5760 KB |
Output is correct |
30 |
Correct |
11 ms |
5888 KB |
Output is correct |
31 |
Correct |
11 ms |
6016 KB |
Output is correct |
32 |
Correct |
39 ms |
9080 KB |
Output is correct |
33 |
Correct |
41 ms |
9208 KB |
Output is correct |
34 |
Correct |
46 ms |
9208 KB |
Output is correct |
35 |
Correct |
242 ms |
21476 KB |
Output is correct |
36 |
Correct |
240 ms |
21516 KB |
Output is correct |
37 |
Correct |
246 ms |
21552 KB |
Output is correct |
38 |
Correct |
182 ms |
20824 KB |
Output is correct |
39 |
Correct |
156 ms |
17628 KB |
Output is correct |
40 |
Correct |
260 ms |
20628 KB |
Output is correct |
41 |
Correct |
229 ms |
24164 KB |
Output is correct |