#include<bits/stdc++.h>
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
typedef long long ll;
ll n,a[100010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	ll s=0,mx=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s+=a[i];
		mx=max(mx,a[i]);
	}
	s-=mx;
	//总和减去最大值计算的是每个点作为断开的两个连通分量最大值中的较小值的总和，由于最大数不可能较小，所以要减去 
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		s+=max(a[x],a[y]);
		//设a[x]为较大值，由于顶点是从大到小删的，所以到x时a[x]是最大的数，删去（x，y）这条边一定会有a[x]的权值 
	}
	cout<<s;
	return 0;
}

根据题目我们可以发现最优解为：先将权值大的的顶点优先与和它连接的点删除。 所以我们就得到了一个时间复杂度 $O(n)$ 的公式：

$\sum_{i=1}^{n}T-\max(T_i)+\sum_{i=1}^{n-1}\max(T_x,T_y)$

证明：因为每一个点至少要和其它数合并一次，所以 $\operatorname{ans}$ 需要加上 $\sum_{i=1}^{n}T$。并且最大的那个数只会被计算到一次（因为最开始就把它给删了），所以 $\operatorname{ans}$ 还需要减去 $\max(T_i)$。然后，权值大的那个数需要在它于小顶点删除的时候又要重新使用（因为题目说：断开一条边的代价为该边连接的两个连通块中各取一个最大权值的顶点之和），所以 $\operatorname{ans}$ 还要加上 $\sum_{i=1}^{n-1}\max(T_x,T_y)$。

$Code$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum,maxa,a[1000005]/*权值*/;
signed main()
{
	cin>>n;//输入
	for(register int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];//总和
		maxa=max(a[i],maxa);//最大值
	}
	sum-=maxa;//利用公式
	for(register int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		sum+=max(a[x],a[y]);//利用公式
	}
	cout<<sum;
	return 0;
}