437D - The Child and Zoo - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second

const int mxn = 1e5+10 ;
int l[mxn] , sz[mxn] ;

inline get(int v){
	return (l[v]==v?v :l[v] = get(l[v])) ;
} 


inline DSU(int v , int u){
	if(sz[u] > sz[v]) swap(v,u) ;
	sz[v] += sz[u] ;
	sz[u] = 0 ;
	l[u] = v ;
	
	return 0 ;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	//input:
	int n , m ;
	cin >> n >> m ;
	
	//update arr sz & l:
	for(int i = 0 ; i < n ; i ++ ){
		sz[i] = 1 ;
		l[i] = i ;
	}
	
	//input (weight):
	int a[n] ;
	for(int i = 0 ; i < n ; i ++ ) cin >> a[i] ;
	
	
	//update pair:
	pair<int,pair<int,int>> edge[m] ;  //{weight,{endpoints}}
	for(int i = 0 ; i < m ; i ++){
		int v , u ;
		cin >> v >> u ;
		v--; u--;
		int mn = min(a[v],a[u]) ;
		edge[i] = make_pair(mn , make_pair(v,u)) ;
	}
	
	//solve:
	long double sum = 0 ;
	sort(edge,edge+m);
	for(int i = m-1 ; i >= 0 ; i --){
		int v = edge[i].s.f ;
		int u = edge[i].s.s ;
		int w = edge[i].f;
		
		v = get(v) ;
		u = get(u) ;
		if( v != u ){
			long double x = (long double)sz[v]*sz[u]*w ;
			sum += x ;
			DSU(v,u) ;
		}
	}
	
	cout << setprecision(6) << fixed;
	cout << (sum*2)/((long double)n*(n-1)) ;
}