#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
#include <queue>
#define pb push_back
using namespace std;
typedef pair<int,int> pp;
struct pt{int u,c;};
typedef vector<int> vec;
typedef vector<pt> vec2;
typedef vector<vec2> graph;
graph path;
int N;
int root;
int dp[200010][3];
void input(){
scanf("%d",&N);
path.assign(N+1,vec2());
int x,y,z;
for(int i=0;i<N-1;i++){
scanf("%d%d%d",&x,&y,&z);
path[x].pb(pt{y,z});
path[y].pb(pt{x,z});
}
}
int getMax2(vec& s){
int Max1=-1e9,Max2=-1e9;
for(int i=0;i<s.size();i++){
if(s[i]>=Max1){
Max2=Max1;
Max1=s[i];
}else if(s[i]>Max2){
Max2=s[i];
}
}
return max(0,Max1+Max2);
}
int getMax1(vec& s){
return *max_element(s.begin(),s.end());
}
void process(int v,int p,int mode){
int sz=path[v].size();
int cnt=sz-(v!=root);
int& ret=dp[v][mode];
ret=0;
if(cnt==0){
if(mode==1)ret=-1e9;
return;
}
vec a;
for(int i=0;i<sz;i++){
int u=path[v][i].u;
int c=path[v][i].c;
if(p==u)continue;
int z = max(dp[u][0],dp[u][1]+c);
ret+=z;
if(mode==0){
a.pb(dp[u][2]+c-z);
}
if(mode==1){
a.pb(dp[u][0]+c-z);
}
}
if(mode==0){
if(cnt>=2){
ret+=getMax2(a);
}
}else if(mode==1){
ret+=getMax1(a);
}
}
void dfs(int v,int p,int mode){
int& ret=dp[v][mode];
if(~ret)return;
for(int i=0;i<path[v].size();i++){
int u=path[v][i].u;
if(u==p)continue;
dfs(u,v,0);
dfs(u,v,1);
dfs(u,v,2);
}
process(v,p,mode);
}
void PS(){
memset(dp,-1,sizeof(dp));
for(int i=1;i<=N;i++){
if(path[i].size()==1){
root=i;
break;
}
}
dfs(root,root,0);
printf("%d\n",dp[root][0]);
}
int main(){
input();
PS();
return 0;
}
Compilation message
beads.cpp: In function 'int getMax2(vec&)':
beads.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.size();i++){
~^~~~~~~~~
beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path[v].size();i++){
~^~~~~~~~~~~~~~~
beads.cpp: In function 'void input()':
beads.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
beads.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
2688 KB |
Output is correct |
3 |
Correct |
3 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2688 KB |
Output is correct |
5 |
Correct |
4 ms |
2688 KB |
Output is correct |
6 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
2688 KB |
Output is correct |
3 |
Correct |
3 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2688 KB |
Output is correct |
5 |
Correct |
4 ms |
2688 KB |
Output is correct |
6 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
2688 KB |
Output is correct |
3 |
Correct |
3 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2688 KB |
Output is correct |
5 |
Correct |
4 ms |
2688 KB |
Output is correct |
6 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
2688 KB |
Output is correct |
3 |
Correct |
3 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2688 KB |
Output is correct |
5 |
Correct |
4 ms |
2688 KB |
Output is correct |
6 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |