#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll, ll> > adj[200005];
pair<ll, ll> dfs(ll u, ll p, ll x)
{
ll a[3]={0, (ll)1e18, (ll)1e18};
for (ll i=0; i<adj[u].size(); i++)
{
ll v=adj[u][i].first, w=adj[u][i].second;
if (v==p)
continue;
pair<ll, ll> r=dfs(v, u, w);
a[2]=min(a[1]+r.first, a[2]+r.second);
a[1]=min(a[0]+r.first, a[1]+r.second);
a[0]+=r.second;
}
return {min(a[0], a[2]), min(a[0]+x, a[1])};
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, sum=0;
cin >> n;
for (ll i=1; i<n; i++)
{
ll u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
sum+=w;
}
cout << sum-dfs(1, 0, 0).first;
}
Compilation message
beads.cpp: In function 'std::pair<long long int, long long int> dfs(long long int, long long int, long long int)':
beads.cpp:8:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | for (ll i=0; i<adj[u].size(); i++)
| ~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5000 KB |
Output is correct |
6 |
Incorrect |
2 ms |
5016 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5000 KB |
Output is correct |
6 |
Incorrect |
2 ms |
5016 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5000 KB |
Output is correct |
6 |
Incorrect |
2 ms |
5016 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5000 KB |
Output is correct |
6 |
Incorrect |
2 ms |
5016 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |