CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko (Network) Sender: MojoLake Submission time: 2021-10-11 13:22:22 Language: C++11 Status: READY Result: 10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#20.01 s2, 3details
#30.23 s3details

### Code

```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int edustaja[200001];
int koko[200001];

int id(int x){
while(edustaja[x] != x){
x = edustaja[x];
}
return x;
}

void liita(int a, int b){
a = id(a);
b = id(b);
if(koko[b] > koko[a])swap(a, b);
koko[a] += koko[b];
edustaja[b] = a;
}

int main(){

for(int i = 1; i <= 200000; ++i){
edustaja[i] = i;
koko[i] = 1;
}
int n; cin >> n;
vector<pair<int, pair<int, int>>> edge_list;
for(int i = 1; i < n; ++i){
int a, b, x;
cin >> a >> b >> x;
edge_list.push_back(make_pair(x, make_pair(a, b)));
}
sort(edge_list.rbegin(), edge_list.rend());
long long int ans = 0;
for(auto edge : edge_list){
int a = edge.second.first;
int b = edge.second.second;
int a_size = koko[id(a)];
int b_size = koko[id(b)];
ans = ans + a_size * b_size * edge.first;
liita(a, b);
}

cout << ans;

return 0;
}
```

### 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

Group: 2, 3

Verdict:

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

correct output
1103702320243776

user output
1794100716608

#### Test 3

Group: 3

Verdict:

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

correct output
1080549209850010931

user output
71708898778419