#include<stdio.h>
#include<algorithm>
#include<vector>
#define M 200010
using namespace std;
vector<int>con[M];
vector<int>len[M];
int D1[M]; // 아무것도 연결 X
int D2[M]; // 자식-나-자식
int D3[M]; // 부모-나-자식, 부모가 연결 X
int D4[M]; // 부모-나-자식, 부모가 연결 O
int p,w,sum,x,y,c,n,big,big1,big2,p1,p2,ch[200010],anc[200010],arr[200010];
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 dfs(int x)
{
int i,j,dap;
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]);
}
//D1 : 아무것도 연결 X
for(i=0;i<con[x].size();i++)
{
big=0;
if(anc[x]==con[x][i]) continue;
big=max(D1[con[x][i]],D2[con[x][i]],D3[con[x][i]]+len[x][i]);
D1[x]+=big;
}
//D2 : 자식-나-자식
big1=-2147483647; big2=-2147483647; sum=0;
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
arr[i]=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
sum+=arr[i];
}
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
w=big1;
big1=max(big1,len[x][i]+D1[con[x][i]]-arr[i],len[x][i]+D2[con[x][i]]-arr[i]);
if(w!=big1) p=i;
}
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i] || p==i) continue;
big2=max(big2,len[x][i]+D1[con[x][i]]-arr[i],len[x][i]+D2[con[x][i]]-arr[i]);
}
if(big1==-2147483647 || big2==-2147483647) D2[x]=sum;
else D2[x]=sum+big1+big2;
//D3 : 부모-나-자식, 부모가 연결X
sum=0;
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
sum+=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
arr[i]=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
}
dap=-2147483647;
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
big=len[x][i]+max(D1[con[x][i]],D2[con[x][i]])-arr[i];
if(dap<big) dap=big;
}
D3[x]=dap+sum;
//D4 : 부모-나-자식, 부모가 연결O
sum=0;
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
sum+=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
arr[i]=max(D1[con[x][i]],D2[con[x][i]],D4[con[x][i]]+len[x][i]);
}
dap=-2147483647;
for(i=0;i<con[x].size();i++)
{
if(anc[x]==con[x][i]) continue;
big=len[x][i]+D1[con[x][i]]-arr[i];
if(dap<big) dap=big;
}
D4[x]=dap+sum;
if(con[x].size()==1 && x!=1) D3[x]=-2147483647, D4[x]=-2147483647;
}
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 dfs(int)':
beads.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++)
~^~~~~~~~~~~~~~
beads.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++)
~^~~~~~~~~~~~~~
beads.cpp:38: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:51:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++)
~^~~~~~~~~~~~~~
beads.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++)
~^~~~~~~~~~~~~~
beads.cpp:67: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:83:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<con[x].size();i++)
~^~~~~~~~~~~~~~
beads.cpp:21:11: warning: unused variable 'j' [-Wunused-variable]
int i,j,dap;
^
beads.cpp: In function 'int main()':
beads.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:98: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
10 ms |
9728 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
