#include <cstdio>
#include <algorithm>
#include <vector>
#define t first
#define c second
using namespace std;
typedef pair<int,int> pp;
vector<pp> e[200010];
vector<int> child[200010];
int pr[200010];
int n;
typedef long long ll;
ll memo[200010][2];
bool exist[200010][2];
void fd(int pos){
int i,s,n;
for(s=e[pos].size(),i=0;i<s;++i){
n=e[pos][i].t;
if(pr[pos]!=n){
pr[n]=pos;
child[pos].push_back(n);
fd(n);
}
}
}
pair<ll,ll> top2(pair<ll,ll> a,ll b){
if(a.second>b) return a;
else {
if(b>a.first) return {b,a.first};
else return {a.first,b};
}
}
ll dfs(int pos,bool can){
if(exist[pos][can]) return memo[pos][can];
// case 1 : tada
int i,s,n;
ll ret=0;
ll ans=0;
for(s=child[pos].size(),i=0;i<s;++i){
n=child[pos][i];
if(pr[pos]!=n) ans+=dfs(n,true);
}
ret=ans;
if(can){
// case 2 : pin this
pair<ll,ll> maxer = {-(1LL<<60),-(1LL<<60)};
ll cs=0;
for(s=e[pos].size(),i=0;i<s;++i){
n=e[pos][i].t;
if(pr[pos]!=n){
cs+=dfs(n,true);
maxer=top2(maxer,e[pos][i].c+dfs(n,false)-dfs(n,true));
}
}
if(maxer.second>-(1LL<<60)) ret=max(ret,cs+maxer.first+maxer.second);
// case 3 : stretch
int j,ss,nn;
for(s=e[pos].size(),i=0;i<s;++i){
n=e[pos][i].t;
if(pr[pos]!=n){
for(ss=e[n].size(),j=0;j<ss;++j){
nn=e[n][j].t;
if(pr[n]!=nn){
ret=max(ret,ans+e[pos][i].c+e[n][j].c+dfs(n,false)-dfs(n,true)+dfs(nn,false)-dfs(nn,true));
}
}
}
}
}
exist[pos][can]=true;
return memo[pos][can]=ret;
}
int main()
{
scanf("%d",&n);
int i,a,b,c;
for(i=1;i<n;++i) scanf("%d%d%d",&a,&b,&c), e[a].push_back({b,c}), e[b].push_back({a,c});
fd(1);
printf("%lld\n",dfs(1,true));
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:77:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<n;++i) scanf("%d%d%d",&a,&b,&c), e[a].push_back({b,c}), e[b].push_back({a,c});
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |