C++14(g++5.4) 解法, 执行用时: 144ms, 内存消耗: 4376K, 提交时间: 2019-12-22 15:31:44

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+7;
int p[MAXN];
long long cnt[MAXN];
int find(int x) {
  if (p[x] == x) return x;
  return p[x] = find(p[x]);
}

void init() {
  for (int i = 0; i < MAXN; i++) p[i] = i, cnt[i] = 1;
}

struct Edge{
  int u, v, w;
};

int main() {
  init();
  int N; cin >> N;
  long long tot = 0;
  vector<Edge> edges(N -1 );
  for (auto &e: edges) cin >> e.u >> e.v >> e.w;
  sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
    return a.w < b.w;
  });
  for (auto &e: edges) {
    int pu = find(e.u), pv = find(e.v);
    tot += (cnt[pu] * cnt[pv] - 1ll) * (e.w + 1ll) + e.w;
    cnt[pu] += cnt[pv];
    p[pv] = pu;
  }
  cout << tot << endl;
}

C++(clang++11) 解法, 执行用时: 51ms, 内存消耗: 4252K, 提交时间: 2021-05-09 13:54:03

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll ans;
ll f[100010],cnt[100010];
struct T{
    ll u,v,w;
}t[100010];
ll fa(ll x){
    if(f[x]!=x) return fa(f[x]);
    else return f[x];
}
bool cmp(T x,T y){ return x.w<y.w;}
int main()
{
    cin>>n;
    for(ll i=1;i<=n-1;i++){
        scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].w);
        ans+=t[i].w;
    }
    for(ll i=1;i<=n;i++) f[i]=i,cnt[i]=1;
    sort(t+1,t+n,cmp);
    for(ll i=1;i<n;i++){
        ll r1=fa(t[i].u);
        ll r2=fa(t[i].v);
        if(r1!=r2){
            ans+=(cnt[r1]*cnt[r2]-1)*(t[i].w+1);
            f[r2]=r1;
            cnt[r1]+=cnt[r2];
        }
    }
    cout<<ans;
}