CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko Sender: intoo Submission time: 2021-10-04 22:45:31 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.23 s3details

### Code

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

using namespace std;
using ll = long long;

ll k[200200], s[200200];
vector<tuple<int, int, int>> q;

int id(int x);
bool same(int a, int b);
void join(int a, int b);

int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
k[i] = i;
s[i] = 1;
}
for (int i = 1; i < n; ++i) {
int a, b, x;
cin >> a >> b >> x;
q.emplace_back(x, a, b);
}
sort(q.begin(), q.end(), greater<tuple<int, int, int>>());
ll t = 0;
for (auto [x, a, b] : q) {
if (same(a, b)) {
t += x;
} else {
t += s[id(a)]*s[id(b)]*x;
join(a, b);
}
}
cout << t << endl;
}

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

bool same(int a, int b)
{
return id(a) == id(b);
}

void join(int a, int b)
{
a = id(a);
b = id(b);
if (s[a] < s[b]) swap(a, b);
k[b] = a;
s[a] += s[b];
}
```

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