Language: C++

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

class Tree{
public:
	priority_queue< vector<LL> , vector< vector<LL> >, 
		greater< vector<LL> > > minLink;
	//コスト1+コスト2,コスト1,コスト2

	vector<LL> other;
	LL COST;

	Tree(){
		COST = 0;
	}

	void set(vector<LL> cost ){//初期値
		//リンクなし、接続点のみ
		other = cost;
		sort( other.begin(), other.end() );
	}
	int getLinkSize(){
		return minLink.size();
	}
	vector<LL> getLink(){
		vector<LL> ans(3,-1);
		if( minLink.size() == 0 ){
			return ans;
		}
		ans = minLink.top();
		return ans;
	}
	int getOtherSize(){
		return other.size();
	}
	LL getOther(){
		if( other.size() ){
			return other[0];
		}
		return -1;
	}
	LL getMinOtherPoint(){
		if( other.size() == 0 ){
			return LINF;
		}
		return other[0];
	}
	vector<LL> getMinOtherPair(){
		vector<LL> ans(2,LINF);
		if( other.size() < 2 ){
			return ans;
		}
		ans[0] = other[0];
		ans[1] = other[1];
		return ans;
	}
	void EraseOther(){
		other.erase( other.begin() );//先頭が一番小さい
	}
	///////////////////
	void CutLink(Tree tree){//切ってくっつける
		//この操作ができるとする。
		
		//接続をきる
		vector<LL> temp = minLink.top();
		minLink.pop();
		
		//ABでつなぎなおす
		LL A,B;
		A = tree.other[0];
		B = tree.other[1];
		vector<LL> LinkTemp(3);
		LinkTemp[0] = temp[1] + A;
		LinkTemp[1] = min(temp[1],A);
		LinkTemp[2] = max(temp[1],A);
		minLink.push( LinkTemp );
		
		LinkTemp[0] = temp[2] + B;
		LinkTemp[1] = min(temp[2],B);
		LinkTemp[2] = max(temp[2],B);
		minLink.push( LinkTemp );

		COST += (A+B);

		int size = tree.other.size();
		int sizeOrg = other.size();
		if( size <= sizeOrg ){
			for(int i=2;i<size;++i){
				other.push_back( tree.other[i] );
			}
		}else{
			tree.EraseOther();
			tree.EraseOther();
			swap(other,tree.other);
			for(int i=0;i<sizeOrg;++i){
				other.push_back( tree.other[i] );
			}
		}
		sort( other.begin(),other.end() );
	}
	/////
	void addLink(Tree tree){
		//他の接続点でくっつける
		LL Apoint = getMinOtherPoint();
		LL Bpoint = tree.getMinOtherPoint();

		EraseOther();
		//tree.EraseOther();
		vector<LL> temp(3);
		temp[0] = Apoint + Bpoint;
		temp[1] = min(Apoint,Bpoint);
		temp[2] = max(Apoint,Bpoint);
		minLink.push( temp );

		COST += temp[0];

		int size = tree.other.size();
		int sizeOrg = other.size();
		if( size <= sizeOrg ){
			for(int i=1;i<size;++i){//先頭は使用済み
				other.push_back( tree.other[i] );
			}
		}else{
			tree.EraseOther();
			swap(other,tree.other);
			for(int i=0;i<sizeOrg;++i){
				other.push_back( tree.other[i] );
			}
		}
		sort( other.begin(),other.end() );
	}
};

void solve(){
	int N,M;
	cin >> N >> M;
	vector<LL> A(N);
	for(int i=0;i<N;++i){
		cin >> A[i];//コスト片
	}
	UnionFind uf(N);
	for(int i=0;i<M;++i){
		int x,y;
		cin >> x >> y;
		uf.add(x,y);
	}
	vector< vector<LL> > cost;
	set<int> root;
	for(int i=0;i<N;++i){
		root.insert( uf.find(i) );//root追加
	}
	vector<int> rootList;
	for(set<int>::iterator itr=root.begin();
		itr != root.end();++itr){
		rootList.push_back( *itr );
	}
	
	int size = root.size();
	vector< vector< LL > > costTree(size);
	/*priority_queue<vector<LL>, vector< vector<LL> >,
		greater< vector<LL> > >
	*/
	int minpqPointIndex = 0;
	int minpqPointSize = -1;
	vector< vector<LL> > minpqPoint;
	for(int i=0;i<N;++i){
		int oya = uf.find(i);
		int id = lower_bound(rootList.begin(),rootList.end(),oya) - rootList.begin();
		
		costTree[id].push_back( A[i] );
		if( id ){
			vector< LL > temp(2);
			temp[0] = A[i];
			temp[1] = id;
			minpqPoint.push_back( temp );
		}
	}
	minpqPointSize = minpqPoint.size();
	sort(minpqPoint.begin(),minpqPoint.end());
	
	size = root.size();
	vector< Tree > fore( size );
	
	int minpqPairIndex = 0;
	int minpqPairSize = -1;
	vector< vector<LL> > minpqPair;//size-1

	for(int i=0;i<size;++i){
		fore[i].set( costTree[i] );
		if( i ){
			vector< LL > res = fore[i].getMinOtherPair();
			vector< LL > temp(2);
			temp[0] = res[0]+res[1];
			temp[1] = i;//id
			temp[0] = min(temp[0],LINF);
			minpqPair.push_back( temp );
		}
	}
	minpqPairSize = minpqPair.size();
	sort( minpqPair.begin(), minpqPair.end() );

	vector<bool> use(size,false);
	use[0] = true;
	///fore[0]に全部くっつける
	int COUNT = size-1;
	vector< LL > pqTemp(2);
	vector< LL > pqPoint(2,LINF);
	vector< LL > pqPair(2,LINF);//和とid pqPair[1]
	
	while(COUNT){//くっつける数

		LL otherCost = LINF;
		LL res = fore[0].getMinOtherPoint();//なければLINF
		
		while( minpqPointIndex < minpqPointSize ){
			pqTemp = minpqPoint[minpqPointIndex];
			if( use[ pqTemp[1] ] == true ){
				++minpqPointIndex;
				continue;
			}
			pqPoint = pqTemp;
			break;
		}
		
		otherCost = res + pqPoint[0];

		////
		LL cutCost = LINF;
		
		if( fore[0].minLink.size() ){//接続があるか
			while( minpqPairIndex < minpqPairSize ){
				pqTemp = minpqPair[minpqPairIndex];
				if( use[ pqTemp[1] ] == true ){
					++minpqPairIndex;
					continue;
				}
				pqPair = pqTemp;
				break;
			}
			cutCost = pqPair[0]+pqPair[1];
		}
		//////////
		if( otherCost >= LINF && cutCost >= LINF ){
			cout << "Impossible" << endl;
			return;
		}
		
		--COUNT;//くっつける
		if( otherCost < cutCost ){
			fore[0].addLink( fore[ pqPoint[1] ] );
			use[ pqPoint[1] ] = true;
		}else{
			fore[0].CutLink( fore[ pqPair[1] ] );
			use[ pqPair[1] ] = true;
		}
	}
	LL ans = fore[0].COST;
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Compiler output:
a.cc: In function 'void solve()':
a.cc:187:9: error: 'UnionFind' was not declared in this scope
  187 |         UnionFind uf(N);
      |         ^~~~~~~~~
a.cc:191:17: error: 'uf' was not declared in this scope
  191 |                 uf.add(x,y);
      |                 ^~
a.cc:196:30: error: 'uf' was not declared in this scope
  196 |                 root.insert( uf.find(i) );//root追加
      |                              ^~
a.cc:213:27: error: 'uf' was not declared in this scope
  213 |                 int oya = uf.find(i);
      |                           ^~