#include<stdio.h>
#include<algorithm>
#include<vector>
#define M 200010
#define N -214748364
using namespace std;
vector<int>con[M];
vector<int>len[M];
int D1[M],D2[M],D3[M],D4[M],D5[M],D6[M];
int dap,p,w,sum,x,y,c,n,big,big1[5],p1,p2,p3,p4,ch[200010],anc[200010],arr[200010],dap2,dap3;
int max(int x,int y,int z)
{
if(x>=y && x>=z) return x;
if(y>=x && y>=z) return y;
return z;
}
void pro_D1(int x)
{
int i,big=0,sum=0,k;
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
k=max(D5[con[x][i]],D3[con[x][i]]+len[x][i]);
big=max(big,max(D1[con[x][i]],D2[con[x][i]])-k,max(D6[con[x][i]],D4[con[x][i]])+len[x][i]-k);
D1[x]+=k; arr[i]=k;
}
D5[x]=D1[x]; D1[x]+=big;
}
void pro_D2(int x,int sw)
{
int i;
for(i=1;i<=4;i++) big1[i]=N;
sum=D5[x];
for(i=0;i<con[x].size();i++){
if(anc[x]==con[x][i]) continue;
w=big1[1]; big1[1]=max(big1[1],len[x][i]+D5[con[x][i]]-arr[i]);
if(w!=big1[1]) p1=i;
}
for(i=0;i<con[x].size();i++){
if(anc[x]==con[x][i] || p1==i) continue;
w=big1[2]; big1[2]=max(big1[2],len[x][i]+D5[con[x][i]]-arr[i]);
if(w!=big1[2]) p2=i;
}
for(i=0;i<con[x].size();i++){
if(anc[x]==con[x][i]) continue;
w=big1[3]; if(sw==1) big1[3]=max(big1[3],len[x][i]+D1[con[x][i]]-arr[i]);
else big1[3]=max(big1[3],len[x][i]+D2[con[x][i]]-arr[i]);
if(w!=big1[3]) p3=i;
}
for(i=0;i<con[x].size();i++){
if(anc[x]==con[x][i] || p3==i) continue;
w=big1[4]; if(sw==1) big1[4]=max(big1[4],len[x][i]+D1[con[x][i]]-arr[i]);
else big1[4]=max(big1[4],len[x][i]+D2[con[x][i]]-arr[i]);
if(w!=big1[4]) p4=i;
}
if((x==1 && con[x].size()<=1) || (x!=1 && con[x].size()<=2)) D2[x]=N;
else{
big=N;
if(p1!=p3 && big<big1[1]+big1[3]) big=big1[1]+big1[3];
if(p1!=p4 && big<big1[1]+big1[4]) big=big1[1]+big1[4];
if(p2!=p3 && big<big1[2]+big1[3]) big=big1[2]+big1[3];
if(p2!=p4 && big<big1[2]+big1[4]) big=big1[2]+big1[4];
D2[x]=max(D2[x],sum+big);
}
}
void pro_D3(int x)
{
int i;
sum=0;
for(i=0;i<con[x].size();i++){
if(anc[x]==con[x][i]) continue;
sum+=max(D5[con[x][i]],D3[con[x][i]]+len[x][i]);
arr[i]=max(D5[con[x][i]],D3[con[x][i]]+len[x][i]);
}
dap=N; dap2=N; dap3=N;
for(i=0;i<con[x].size();i++){
if(anc[x]==con[x][i]) continue;
big=len[x][i]+D5[con[x][i]]-arr[i]; if(dap<big) dap=big;
big=len[x][i]+D1[con[x][i]]-arr[i]; if(dap2<big) dap2=big;
big=len[x][i]+D2[con[x][i]]-arr[i]; if(dap3<big) dap3=big;
}
D3[x]=dap+sum; D6[x]=dap2+sum; D4[x]=dap3+sum;
}
void dfs(int x)
{
int i,j;
ch[x]=1;
for(i=0;i<con[x].size();i++){
if(ch[con[x][i]]==1){anc[x]=con[x][i]; continue;}
dfs(con[x][i]);
}
pro_D1(x); pro_D2(x,1); pro_D2(x,2); pro_D3(x);
if(con[x].size()==1 && x!=1) D3[x]=N, D4[x]=N, D6[x]=N;
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<n;i++){
scanf("%d %d %d",&x,&y,&c);
con[x].push_back(y); con[y].push_back(x);
len[x].push_back(c); len[y].push_back(c);
}
dfs(1);
printf("%d",max(D1[1],D2[1]));
return 0;
}
Compilation message
beads.cpp: In function 'void pro_D1(int)':
beads.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++)
~^~~~~~~~~~~~~~
beads.cpp:19:17: warning: unused variable 'sum' [-Wunused-variable]
int i,big=0,sum=0,k;
^~~
beads.cpp: In function 'void pro_D2(int, int)':
beads.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:39:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:44:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:50:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp: In function 'void pro_D3(int)':
beads.cpp:70:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int)':
beads.cpp:88:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++){
~^~~~~~~~~~~~~~
beads.cpp:86:11: warning: unused variable 'j' [-Wunused-variable]
int i,j;
^
beads.cpp: In function 'int main()':
beads.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&x,&y,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
11 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
11 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9728 KB |
Output is correct |
13 |
Correct |
10 ms |
9728 KB |
Output is correct |
14 |
Correct |
10 ms |
9728 KB |
Output is correct |
15 |
Correct |
10 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9772 KB |
Output is correct |
17 |
Correct |
10 ms |
9728 KB |
Output is correct |
18 |
Correct |
11 ms |
9728 KB |
Output is correct |
19 |
Correct |
10 ms |
9728 KB |
Output is correct |
20 |
Correct |
11 ms |
9700 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
11 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9728 KB |
Output is correct |
13 |
Correct |
10 ms |
9728 KB |
Output is correct |
14 |
Correct |
10 ms |
9728 KB |
Output is correct |
15 |
Correct |
10 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9772 KB |
Output is correct |
17 |
Correct |
10 ms |
9728 KB |
Output is correct |
18 |
Correct |
11 ms |
9728 KB |
Output is correct |
19 |
Correct |
10 ms |
9728 KB |
Output is correct |
20 |
Correct |
11 ms |
9700 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
23 |
Correct |
14 ms |
10240 KB |
Output is correct |
24 |
Correct |
14 ms |
10240 KB |
Output is correct |
25 |
Correct |
14 ms |
10240 KB |
Output is correct |
26 |
Correct |
19 ms |
10804 KB |
Output is correct |
27 |
Correct |
19 ms |
10880 KB |
Output is correct |
28 |
Correct |
17 ms |
10880 KB |
Output is correct |
29 |
Correct |
18 ms |
10880 KB |
Output is correct |
30 |
Correct |
20 ms |
10880 KB |
Output is correct |
31 |
Correct |
17 ms |
10980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
11 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9728 KB |
Output is correct |
13 |
Correct |
10 ms |
9728 KB |
Output is correct |
14 |
Correct |
10 ms |
9728 KB |
Output is correct |
15 |
Correct |
10 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9772 KB |
Output is correct |
17 |
Correct |
10 ms |
9728 KB |
Output is correct |
18 |
Correct |
11 ms |
9728 KB |
Output is correct |
19 |
Correct |
10 ms |
9728 KB |
Output is correct |
20 |
Correct |
11 ms |
9700 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
23 |
Correct |
14 ms |
10240 KB |
Output is correct |
24 |
Correct |
14 ms |
10240 KB |
Output is correct |
25 |
Correct |
14 ms |
10240 KB |
Output is correct |
26 |
Correct |
19 ms |
10804 KB |
Output is correct |
27 |
Correct |
19 ms |
10880 KB |
Output is correct |
28 |
Correct |
17 ms |
10880 KB |
Output is correct |
29 |
Correct |
18 ms |
10880 KB |
Output is correct |
30 |
Correct |
20 ms |
10880 KB |
Output is correct |
31 |
Correct |
17 ms |
10980 KB |
Output is correct |
32 |
Correct |
74 ms |
14696 KB |
Output is correct |
33 |
Correct |
63 ms |
14712 KB |
Output is correct |
34 |
Correct |
60 ms |
14588 KB |
Output is correct |
35 |
Correct |
394 ms |
29096 KB |
Output is correct |
36 |
Correct |
411 ms |
29056 KB |
Output is correct |
37 |
Correct |
645 ms |
29088 KB |
Output is correct |
38 |
Correct |
283 ms |
30940 KB |
Output is correct |
39 |
Correct |
543 ms |
30672 KB |
Output is correct |
40 |
Correct |
316 ms |
30308 KB |
Output is correct |
41 |
Correct |
383 ms |
31676 KB |
Output is correct |