#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[200005];
int n;
int dp[200005][2];
int f(int x, int m, int pa, int e){
if(~dp[x][m]) return dp[x][m];
if(m == 0){
int *dp2[3];
for (int i=0; i<3; i++) {
dp2[i] = new int[graph[x].size()]();
}
int cnt = 0;
for (int i=0; i<graph[x].size(); i++) {
pi t = graph[x][i];
if(t.second == pa){
if(i){
for (int j=0; j<3; j++) {
dp2[j][i] = dp2[j][i-1];
}
}
continue;
}
int classic = f(t.second,0,x,t.first);
int pick = f(t.second,1,x,t.first);
int free = t.first;
dp2[0][i] = (i ? dp2[0][i-1] : 0) + max(classic,pick);
if(cnt == 0) dp2[1][i] = classic + free;
else dp2[1][i] = max(dp2[1][i-1] + max(classic,pick),dp2[0][i-1] + classic + free);
if(cnt >= 2) dp2[2][i] = dp2[2][i-1] + max(classic,pick);
if(cnt) dp2[2][i] = max(dp2[2][i],dp2[1][i-1] + classic + free);
cnt++;
}
int ret = max(dp2[0][graph[x].size()-1],dp2[2][graph[x].size()-1]);
for(int i=0; i<3; i++){
delete[] dp2[i];
}
return dp[x][m] = ret;
}
else{
int ret = 0;
int addi = 0;
for(pi i : graph[x]){
if(i.second == pa) continue;
int classic = max(f(i.second,0,x,i.first),f(i.second,1,x,i.first));
int pick = f(i.second,0,x,i.first) + i.first + e;
ret += classic;
addi = max(addi,pick - classic);
}
return dp[x][m] = ret + addi;
}
}
int main(){
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
for (int i=0; i<n-1; i++) {
int s,e,x;
scanf("%d %d %d",&s,&e,&x);
graph[s].push_back(pi(x,e));
graph[e].push_back(pi(x,s));
}
printf("%d",f(1,0,0,0));
}
Compilation message
beads.cpp: In function 'int f(int, int, int, int)':
beads.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<graph[x].size(); i++) {
~^~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&s,&e,&x);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6528 KB |
Output is correct |
2 |
Correct |
7 ms |
6528 KB |
Output is correct |
3 |
Correct |
6 ms |
6528 KB |
Output is correct |
4 |
Correct |
7 ms |
6528 KB |
Output is correct |
5 |
Correct |
6 ms |
6528 KB |
Output is correct |
6 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6528 KB |
Output is correct |
2 |
Correct |
7 ms |
6528 KB |
Output is correct |
3 |
Correct |
6 ms |
6528 KB |
Output is correct |
4 |
Correct |
7 ms |
6528 KB |
Output is correct |
5 |
Correct |
6 ms |
6528 KB |
Output is correct |
6 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6528 KB |
Output is correct |
2 |
Correct |
7 ms |
6528 KB |
Output is correct |
3 |
Correct |
6 ms |
6528 KB |
Output is correct |
4 |
Correct |
7 ms |
6528 KB |
Output is correct |
5 |
Correct |
6 ms |
6528 KB |
Output is correct |
6 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6528 KB |
Output is correct |
2 |
Correct |
7 ms |
6528 KB |
Output is correct |
3 |
Correct |
6 ms |
6528 KB |
Output is correct |
4 |
Correct |
7 ms |
6528 KB |
Output is correct |
5 |
Correct |
6 ms |
6528 KB |
Output is correct |
6 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |