uvalive_6070.cpp

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct UnionFind {
  vector<ll> sz, par, cost;
  UnionFind(ll n):sz(n, 1), par(n), cost(n, 0) {
    iota(par.begin(), par.end(), 0);
  }
  ll find(ll x) {
    if(par[x] == x) return x;
    ll r = find(par[x]);
    if(r != par[x]) cost[x] += cost[par[x]];
    return par[x] = r;
  }
  void unite(ll x, ll y, ll w) {
    x = find(x), y = find(y);
    if(sz[x] < sz[y]) swap(x, y);
    cost[x] += sz[y]*w;
    cost[y] += sz[x]*w - cost[x];
    sz[x] += sz[y];
    par[y] = x;
  }
  ll get(ll x) {
    ll r = find(x);
    return cost[x] + (r == x ? 0 : cost[r]);
  }
};

using edge = tuple<ll, ll, ll>;

int main() {
  ll N;
  while(scanf("%lld", &N) != EOF) {
    vector<edge> es;
    for(ll i = 1; i < N; ++i) {
      ll a, b, c;
      scanf("%lld %lld %lld", &a, &b, &c);
      --a, --b;
      es.emplace_back(c, a, b);
    }
    sort(es.rbegin(), es.rend());
    UnionFind uf(N);
    for(edge e : es) {
      ll a, b, c;
      tie(c, a, b) = e;
      uf.unite(a, b, c);
    }
    ll ans = 0;
    for(ll i = 0; i < N; ++i) ans = max(ans, uf.get(i));
    printf("%lld\n", ans);
  }
  return 0;
}