CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko (Network) Sender: Anttono Submission time: 2021-10-06 20:51:56 Language: C++11 Status: READY Result: 100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.24 s3details

### Code

```#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define N 200001

int n;
ll r;
vector<pair<ll,pair<int,int>>> s;
pair<bool,ll> v[N];

int main()
{
cin>>n;
int a,b;
ll x;
for(int i=1;i<n;i++)
{
cin>>a>>b>>x;
s.push_back(make_pair(x,make_pair(a,b)));
v[i] = make_pair(false, 1);
}
v[n] = make_pair(false, 1);
sort(s.rbegin(), s.rend());
for(auto p : s)
{
int a = p.second.first;
int b = p.second.second;
ll x = p.first;
int la=0;
while(v[a].first)
{
a = v[a].second;
la++;
}
int lb=0;
while(v[b].first)
{
b = v[b].second;
lb++;
}
r += x * v[a].second * v[b].second;
if(la>lb)
{
v[a].second += v[b].second;
v[b].first = true;
v[b].second = a;
}
else
{
v[b].second += v[a].second;
v[a].first = true;
v[a].second = b;
}
}
cout<<r;
}
```

### Test details

#### Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

#### Test 2

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
1103702320243776

#### Test 3

Group: 3

Verdict: ACCEPTED

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
1080549209850010931