@BOB 6529 RE???? #include<bits/stdc++.h> using namespace std; typedef long long lint; lint n; lint fa[100005], num[100005]; lint ans; struct T { lint v, u, w; }e[100005]; bool cmp(const T&a, const T&b) { return a.w<b.w; } lint find(lint x) { return x==fa[x] ? x : fa[x] = find(x); } int main() { cin>>n; for(lint i=1;i<=n;i++) { fa[i] = i; num[i] = 1; } for(lint i=1;i<=n-1;i++) cin>>e[i].v>>e[i].u>>e[i].w, ans+=e[i].w; sort(e+1,e+n,cmp); for(lint i=1;i<=n-1;i++) { lint x = find(e[i].u); lint y = find(e[i].v); if(x!=y) { ans += (num[x]*num[y]-1)*(e[i].w+1); fa[x] = y; num[y] += num[x]; } } cout<<ans<<"\n"; return 0; }