C++ 解法, 执行用时: 269ms, 内存消耗: 45140K, 提交时间: 2021-11-19 20:41:03

//#define LOCAL
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;
const int N = 1e6 + 100;
const int inf = 1e9;
//const ll inf = 1e18
const ll mod = 998244353;//1e9 + 7

#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


int n, rnk[N];
ll a[N], dis[N];
pii b[N];
VI adj[N];

ll cost[N];

void bfs(int x)
{
	queue<int> q;
	trav(v, adj[x])
	{
		if(a[v] <= a[x])
			break;
		if(cost[v] > a[x] * 2)
		{
			cost[v] = a[x] * 2;
			dis[v] = 2;
			q.push(v);
		}
	}
	int nw;
	while(!q.empty())
	{
		nw = q.front();
		q.pop();
		trav(v, adj[nw])
		{
			if(a[v] <= a[x])
				continue;
			if(cost[v] > a[x] * (dis[nw] + 1))
			{
				cost[v] = a[x] * (dis[nw] + 1);
				dis[v] = dis[nw] + 1;
				q.push(v);
			}
		}
	}
	return;
}

void sol()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for(int i = 1; i <= n; i++)
	{
		b[i].fi = a[i];
		b[i].sc = i;
	}
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++)
		rnk[b[i].sc] = i;
	for(int i = 1; i <= n; i++)
	{
		sort(all(adj[i]), [](int x, int y)
		{
			return rnk[x] > rnk[y];
		}
		);
	}
	memset(cost, 63, sizeof cost);
	for(int i = 1; i <= n; i++)
	{
		bfs(b[i].sc);
		//cerr << "!!!" << b[i].sc << '\n';
//		for(int i =1 ;i <= n; i++)
//			cerr << dis[i] << ' ';
//		cerr << '\n';
	}
	ll res = 0;
	for(int i = 1; i <= n; i++)
	{
		if(cost[i] >= 1e18)
			continue;
		res += cost[i] + a[i];
	}
	cout << res << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	int tt;
//	cin >> tt;
//	while(tt--)
		sol();
}