CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko Sender: Mahtimursu Submission time: 2021-10-04 15:43:45 Language: C++17 Status: READY Result: 100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.11 s3details

### Code

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

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

vector<pair<ll, pair<int, int>>> edges;

int rep[200001];
int sz[200001];

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

void join(int a, int b) {
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
rep[b] = a;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b, c;
cin >> a >> b >> c;
edges.push_back({c, { a, b }});
}

for (int i = 1; i <= n; ++i) {
sz[i] = 1;
rep[i] = i;
}

sort(edges.rbegin(), edges.rend());

ll ans = 0;

for (auto p : edges) {
ll w = p.first;
int a = p.second.first;
int b = p.second.second;
a = id(a);
b = id(b);
ans += sz[a] * sz[b] * w;
join(a, b);
}

cout << ans << "\n";

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

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