#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int N;
vector<pii> adj[MAXN+10];
ll dp1[MAXN+10], dp2[MAXN+10];
void dfs(int now, int bef, int par)
{
vector<ll> V;
ll S=0;
for(pii nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now, nxt.second);
S+=max(dp1[nxt.first], dp2[nxt.first]);
V.push_back(dp2[nxt.first]+nxt.second-max(dp1[nxt.first], dp2[nxt.first]));
}
sort(V.begin(), V.end(), greater<ll>());
dp2[now]=S;
if(V.size()>1 && V[0]+V[1]>=0) dp2[now]+=V[0]+V[1];
dp1[now]=S;
if(V.size()>0 && V[0]>=0) dp1[now]+=max(V[0], 0ll), dp1[now]+=par;
//printf("%d %lld %lld\n", now, dp1[now], dp2[now]);
}
int main()
{
int i, j;
scanf("%d", &N);
for(i=1; i<N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1, 1, 0);
printf("%lld", dp2[1]);
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:37:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
beads.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
beads.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
4984 KB |
Output is correct |
3 |
Correct |
6 ms |
4984 KB |
Output is correct |
4 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |