RT

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct jjj{
	int a,f,z,id,in;
}ak[1000005];
bool cmp(jjj qq,jjj ss){
	return qq.a<ss.a;
}
signed main(){
	scanf("%lld",&n);
	for(int i(1);i<=n;i++)
	scanf("%lld",&ak[i].a),ak[i].id=i;
	for(int i(1);i<n;i++)
	scanf("%lld%lld",&ak[i].f,&ak[i].z),ak[ak[i].f].in++,ak[ak[i].z].in++;
	sort(ak+1,ak+n+1,cmp);
	int k1=ak[(1+n)/2].a,k2=ak[(1+n)/2+1].a;
	long long ans1=0,ans2=0;
	for(int i(1);i<=n;i++)
	ans1+=ak[ak[i].id].in*abs(ak[i].a-k1);
	for(int i(1);i<=n;i++)
	ans2+=ak[ak[i].id].in*abs(ak[i].a-k2);
	if(n&1)
	cout<<ans1;
	else
	cout<<min(ans1,ans2);
	return 0;
}