#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=2e5+5;
int n;
vector <pii> ls[N];
ll dp[N][2];
void rek(int node, int fl, int par) {
if (dp[node][fl]!=-1) return;
for (pii sus:ls[node]) {
if (sus.X!=par) {
rek(sus.X, 0, node);
rek(sus.X, 1, node);
}
}
ll maxi[2]={-MAX, -MAX};
ll sum0=0;
for (pii sus:ls[node]) {
ll x;
if (sus.X==par) {
if (fl) continue;
x=sus.Y;
}
else {
sum0+=dp[sus.X][0];
x=dp[sus.X][1]-dp[sus.X][0]+sus.Y;
}
for (int i=0; i<2; ++i) if (x>maxi[i]) swap(x, maxi[i]);
}
dp[node][fl]=max(sum0, sum0+maxi[0]+maxi[1]);
}
void load() {
scanf("%d", &n);
for (int i=0; i<n-1; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
ls[a].pb(mp(b, c));
ls[b].pb(mp(a, c));
}
}
int main() {
load();
memset(dp, -1, sizeof dp);
rek(1, 1, 1);
printf("%lld\n", dp[1][1]);
return 0;
}
Compilation message
beads.cpp: In function 'void load()':
beads.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
50 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
beads.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | scanf("%d %d %d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8172 KB |
Output is correct |
2 |
Correct |
5 ms |
8172 KB |
Output is correct |
3 |
Correct |
5 ms |
8172 KB |
Output is correct |
4 |
Correct |
5 ms |
8172 KB |
Output is correct |
5 |
Correct |
6 ms |
8172 KB |
Output is correct |
6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8172 KB |
Output is correct |
2 |
Correct |
5 ms |
8172 KB |
Output is correct |
3 |
Correct |
5 ms |
8172 KB |
Output is correct |
4 |
Correct |
5 ms |
8172 KB |
Output is correct |
5 |
Correct |
6 ms |
8172 KB |
Output is correct |
6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8172 KB |
Output is correct |
2 |
Correct |
5 ms |
8172 KB |
Output is correct |
3 |
Correct |
5 ms |
8172 KB |
Output is correct |
4 |
Correct |
5 ms |
8172 KB |
Output is correct |
5 |
Correct |
6 ms |
8172 KB |
Output is correct |
6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8172 KB |
Output is correct |
2 |
Correct |
5 ms |
8172 KB |
Output is correct |
3 |
Correct |
5 ms |
8172 KB |
Output is correct |
4 |
Correct |
5 ms |
8172 KB |
Output is correct |
5 |
Correct |
6 ms |
8172 KB |
Output is correct |
6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |