#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
int n;
vector<pi> graph[200005];
int dp[200005][4];
int f(int x, int m, int p){
if(~dp[x][m]) return dp[x][m];
if(m >= 2){
int maxv = -1e9, sum = 0;
for(int i=0; i<graph[x].size(); i++){
int pos = graph[x][i].second;
if(pos == p) continue;
int tmp = max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
sum += tmp;
maxv = max(maxv, f(pos, m-2, x) + graph[x][i].first - tmp);
}
return dp[x][m] = sum + maxv;
}
else if(m == 1){
int ret = 0;
for(int i=0; i<graph[x].size(); i++){
int pos = graph[x][i].second;
if(pos == p) continue;
ret += max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
}
return dp[x][m] = ret;
}
else{
int sum = 0, maxv = 0;
for(int i=0; i<graph[x].size(); i++){
int pos = graph[x][i].second;
if(pos == p) continue;
int tmp1 = max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
int tmp2 = max(f(pos, 0, x), f(pos, 2, x) + graph[x][i].first);
sum += tmp1;
maxv = max(maxv, tmp2 - tmp1);
}
int ret = sum + maxv;
vector<pi> tmp;
sum = 0;
for(int i=0; i<graph[x].size(); i++){
int pos = graph[x][i].second;
if(pos == p) continue;
int tmp1 = max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
int tmp2 = f(pos, 0, x) + graph[x][i].first;
int tmp3 = f(pos, 1, x) + graph[x][i].first;
tmp.push_back(pi(tmp2 - tmp1, tmp3 - tmp1));
sum += tmp1;
}
int pmax = -1e9, smax = -1e9;
for(int i=0; i<tmp.size(); i++){
ret = max(ret, sum + tmp[i].first + pmax);
pmax = max(pmax, tmp[i].second);
}
for(int i=tmp.size()-1; i>=0; i--){
ret = max(ret, sum + tmp[i].first + smax);
smax = max(smax, tmp[i].second);
}
return dp[x][m] = ret;
}
}
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));
}
Compilation message
beads.cpp: In function 'int f(int, int, int)':
beads.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<graph[x].size(); i++){
~^~~~~~~~~~~~~~~~
beads.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<graph[x].size(); i++){
~^~~~~~~~~~~~~~~~
beads.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<graph[x].size(); i++){
~^~~~~~~~~~~~~~~~
beads.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<graph[x].size(); i++){
~^~~~~~~~~~~~~~~~
beads.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<tmp.size(); i++){
~^~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:89:8: 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 |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
8 ms |
8108 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
9 ms |
8192 KB |
Output is correct |
7 |
Correct |
8 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
10 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
9 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
8 ms |
8108 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
9 ms |
8192 KB |
Output is correct |
7 |
Correct |
8 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
10 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
9 ms |
8192 KB |
Output is correct |
13 |
Correct |
17 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
9 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
9 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
10 ms |
8192 KB |
Output is correct |
22 |
Correct |
9 ms |
8220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
8 ms |
8108 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
9 ms |
8192 KB |
Output is correct |
7 |
Correct |
8 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
10 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
9 ms |
8192 KB |
Output is correct |
13 |
Correct |
17 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
9 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
9 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
10 ms |
8192 KB |
Output is correct |
22 |
Correct |
9 ms |
8220 KB |
Output is correct |
23 |
Correct |
11 ms |
8320 KB |
Output is correct |
24 |
Correct |
12 ms |
8320 KB |
Output is correct |
25 |
Correct |
11 ms |
8320 KB |
Output is correct |
26 |
Correct |
17 ms |
8448 KB |
Output is correct |
27 |
Correct |
15 ms |
8448 KB |
Output is correct |
28 |
Correct |
14 ms |
8704 KB |
Output is correct |
29 |
Correct |
14 ms |
8576 KB |
Output is correct |
30 |
Correct |
15 ms |
8596 KB |
Output is correct |
31 |
Correct |
15 ms |
9088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
8 ms |
8192 KB |
Output is correct |
3 |
Correct |
8 ms |
8192 KB |
Output is correct |
4 |
Correct |
8 ms |
8108 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
9 ms |
8192 KB |
Output is correct |
7 |
Correct |
8 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
10 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
9 ms |
8192 KB |
Output is correct |
13 |
Correct |
17 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
9 ms |
8192 KB |
Output is correct |
16 |
Correct |
9 ms |
8192 KB |
Output is correct |
17 |
Correct |
9 ms |
8192 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
9 ms |
8192 KB |
Output is correct |
20 |
Correct |
9 ms |
8192 KB |
Output is correct |
21 |
Correct |
10 ms |
8192 KB |
Output is correct |
22 |
Correct |
9 ms |
8220 KB |
Output is correct |
23 |
Correct |
11 ms |
8320 KB |
Output is correct |
24 |
Correct |
12 ms |
8320 KB |
Output is correct |
25 |
Correct |
11 ms |
8320 KB |
Output is correct |
26 |
Correct |
17 ms |
8448 KB |
Output is correct |
27 |
Correct |
15 ms |
8448 KB |
Output is correct |
28 |
Correct |
14 ms |
8704 KB |
Output is correct |
29 |
Correct |
14 ms |
8576 KB |
Output is correct |
30 |
Correct |
15 ms |
8596 KB |
Output is correct |
31 |
Correct |
15 ms |
9088 KB |
Output is correct |
32 |
Correct |
54 ms |
10032 KB |
Output is correct |
33 |
Correct |
55 ms |
9976 KB |
Output is correct |
34 |
Correct |
62 ms |
9948 KB |
Output is correct |
35 |
Correct |
298 ms |
15736 KB |
Output is correct |
36 |
Correct |
253 ms |
15608 KB |
Output is correct |
37 |
Correct |
259 ms |
15736 KB |
Output is correct |
38 |
Correct |
211 ms |
19084 KB |
Output is correct |
39 |
Correct |
232 ms |
17672 KB |
Output is correct |
40 |
Correct |
267 ms |
16832 KB |
Output is correct |
41 |
Correct |
332 ms |
23280 KB |
Output is correct |