记录编号	593624	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3074.动物园	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	4.674 s
提交时间	2024-09-06 01:22:58	内存使用	10.33 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,q,f[100010],a[100010],k[100010],ans;
struct node{
	long long x;
	long long y;
	long long z;
}e[1000010];
long long cmp(node A,node B){
	if(A.z==B.z) 
return A.x<B.x;
	return A.z>B.z;
}
long long fi(long long x){
	if(f[x]==x){
		return x;
	}
	return f[x]=fi(f[x]);
}
void hb(long long x,long long y,long long z){
	long long u=fi(x),v=fi(y);
	if(u==v){
//	  ans+=2*z;
	  return;
	}
//	if(v!=y&&u==x){
//		swap(x,y);
//		swap(u,v);
//	}
//	cout<<x<<" "<<y<<" "<<k[u]<<" "<<k[v]<<" "<<z<<" "<<ans<<endl;
	ans+=(k[u]*k[v])*z*2;
	k[u]+=k[v];
	f[f[y]]=f[u];
}
int main(){
	freopen("happyzoo.in","r",stdin);
    freopen("happyzoo.out","w",stdout);
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		f[i]=i;
		cin>>a[i];
		k[i]=1;
	}
	for(long long i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y;
		if(e[i].y<e[i].x)
		swap(e[i].x,e[i].y);
		e[i].z=min(a[e[i].x],a[e[i].y]);
//		if(i>6)
//		cout<<e[i].x<<e[i].y<<".";
	}
	sort(e+1,e+m+1,cmp);
	for(long long i=1;i<=m;i++){
		hb(e[i].x,e[i].y,e[i].z);
//		cout<<e[i].x<<" "<<e[i].y<<" "<<e[i].z<<" "<<ans<<endl;
	}
	cout<<ans;
	return 0;
}