#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define maxn 10100
#define debug
#define pii pair<int,int>
vector<pii> L[maxn];
int dp[2][2][maxn];
int get(int hat,int need,int vx,int p=-1){
// fprintf(stderr,"%d %d %d\n",need,vx,p);
int &r = dp[hat][need][vx];
if(r+1) return r;
int st=0;
vector<int> vs;
int fi = L[vx].size();
if(vx)fi--;
r = 0;
int l = L[vx].size();
if(need == 0){
if(hat && fi >= 2) {
int stot= 0;
vector<int> ss;
int bestj=-1e7, whoj, best2=-1e7;
for(int k=0;k<l;k++){
int to = L[vx][k].first; // fprintf(stderr,"to %d\n",to);
int val = max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second);
if(to != p)stot += val,
ss.pb(val);
else ss.pb(0);
int up = L[vx][k].second + get(1,0,to,vx);
up = up-val;
if(vx ==5 && up==-1) debug("!!! to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
if(up > bestj){
best2 = bestj;
bestj= up;
whoj = k;
}
else if(up > best2) best2 = up;
}
for(int i=0;i<l;i++){//for(int j=i+1;j<l;j++){
int A = L[vx][i].first;//, B = L[vx][j].first;
if(A == p) continue;
int s = L[vx][i].second + get(0,0,A,vx);
int add = bestj;
if(whoj == i) add = best2;
s += stot - ss[i] + add;
r = max(r,s);
if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
}
}
st=0;
vs.clear();
for(int k=0;k<l;k++){
int to = L[vx][k].first;
if(to != p) st += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second),
vs.pb(max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second));
else vs.pb(0);
}
int no = 0;
for(int spec=0;spec<l;spec++){
no=0;
int to = L[vx][spec].first;
if(to == p) continue;
no += max(get(hat,0,to,vx), get(hat,1,to,vx) + L[vx][spec].second);
/* for(int k=0;k<l;k++){
int to = L[vx][k].first;
int hh = (hat && (spec==k));
if(to != p) no += max(get(hh,0,to,vx), get(hh,1,to,vx) + L[vx][k].second);
}*/
no += st - vs[spec];
r = max(r,no);
}
r = max(r,no);
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
return r;
}
if(L[vx].size()==1){
r = -1e7;
return r;
}
st = 0;
vs.clear();
for(int j=0;j<L[vx].size();j++){
int to = L[vx][j].first;
if(to == p ) vs.pb(0);
else
st += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][j].second),
vs.pb(max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][j].second));
}
for(int i=0;i<L[vx].size();i++){
int s = 0;
if(L[vx][i].first == p) continue;
s = L[vx][i].second + get(hat,0,L[vx][i].first,vx);
s += st - vs[i];
r = max(r,s);
}
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
return r;
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c), a--, b--;
L[a].pb(pii(b,c));
L[b].pb(pii(a,c));
}
memset(dp,-1,sizeof(dp));
printf("%d\n",get(1,0,0));
//printf("%d\n",get(0,0,1));
}
Compilation message
beads.cpp: In function 'int get(int, int, int, int)':
beads.cpp:44:77: warning: left operand of comma operator has no effect [-Wunused-value]
if(vx ==5 && up==-1) debug("!!! to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
^~
beads.cpp:44:111: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx ==5 && up==-1) debug("!!! to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
^
beads.cpp:44:96: warning: value computed is not used [-Wunused-value]
if(vx ==5 && up==-1) debug("!!! to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
beads.cpp:63:78: warning: left operand of comma operator has no effect [-Wunused-value]
if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
^
beads.cpp:63:80: warning: right operand of comma operator has no effect [-Wunused-value]
if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
^
beads.cpp:63:82: warning: right operand of comma operator has no effect [-Wunused-value]
if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
^~~~
beads.cpp:63:88: warning: right operand of comma operator has no effect [-Wunused-value]
if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
^~~~~
beads.cpp:91:48: warning: left operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^~~
beads.cpp:91:52: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^~~~
beads.cpp:91:57: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^~
beads.cpp:91:60: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^
beads.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<L[vx].size();j++){
~^~~~~~~~~~~~~
beads.cpp:110:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<L[vx].size();i++){
~^~~~~~~~~~~~~
beads.cpp:117:45: warning: left operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^~~
beads.cpp:117:49: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^~~~
beads.cpp:117:54: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^~
beads.cpp:117:57: warning: right operand of comma operator has no effect [-Wunused-value]
if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
^
beads.cpp: In function 'int main()':
beads.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:127:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&a,&b,&c), a--, b--;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
beads.cpp: In function 'int get(int, int, int, int)':
beads.cpp:59:17: warning: 'whoj' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(whoj == i) add = best2;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
760 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
764 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
760 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
764 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
760 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
764 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
760 KB |
Output is correct |
| 7 |
Correct |
2 ms |
760 KB |
Output is correct |
| 8 |
Correct |
2 ms |
760 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Correct |
2 ms |
764 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
