提出 #25037741

---

ソースコード 拡げる

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll, null_type, less_equal<>, rb_tree_tag,
//    tree_order_statistics_node_update> ordered_set;

ld eps = (ld) 1 / 1e6;
ll inf_ll = 1e18 + 100, mod1 = 1e9 + 7, mod2 = 998244353;
ll mersen_mod = 2305843009213693951;

ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll add(ll a, ll b, ll mod) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
ll sub(ll a, ll b, ll mod) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
ll binpow(ll a, ll b, ll mod) {
  return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod :
              sqr(binpow(a, b / 2, mod)) % mod) : 1;
}
ll binmult(ll a, ll b, ll mod) {
  return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod :
              (2 * binmult(a, b / 2, mod)) % mod) : 0;
}

/// Code here
vector<ll> gr[100001];
ll ans, mn[100001];
struct edg { ll x, y, z; };
vector<edg> vc;
unordered_map<ll, vector<ll>> dsu;

int main() {
  fast_io;
  ll n, i, x, y, z;
  cin >> n;
  for (i = 1; i <= n; i++) dsu[i] = {i}, mn[i] = i;
  for (i = 1; i < n; i++) {
    cin >> x >> y >> z;
    vc.pb({x, y, z});
    gr[x].pb(y), gr[y].pb(x);
  }
  sort(all(vc), [](edg a, edg b) { return a.z < b.z; });
  for (auto f : vc) {
    x = mn[f.x];
    y = mn[f.y];
    z = f.z;
    if (x == y) continue;
    if (dsu[x].size() < dsu[y].size()) swap(x, y);
    ans += dsu[x].size() * dsu[y].size() * z;
    for (auto g : dsu[y]) {
      dsu[x].pb(g);
      mn[g] = x;
    }
    dsu.erase(y);
  }
  cout << ans;
  //cerr << '\n' << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << '\n';
  return 0;
}

提出情報

ジャッジ結果