link:https://www.luogu.com.cn/record/123518186

#include<bits/stdc++.h>
using namespace std;

#define MAXN 5005
int n,ru,rv;
int siz[MAXN];
long long f[MAXN],dper[MAXN][MAXN];

vector<int> so[MAXN];

void dp(int fa,int u){
	dper[u][0]=0;
	for(auto v:so[u]){
		if(v==fa){
			continue;
		}
		dp(u,v);
		for(int del=1;del<=siz[v]-1;del++){
			for(int up=siz[u];up>=0;up--){
				int un=up+del;
				dper[u][un]=min(dper[u][un],dper[u][up]+dper[v][del]);
			}
		}
		siz[u]+=siz[v];
	}
	for(int i=1;i<=siz[u];i++){
		int lft=siz[u]-i;
		dper[u][siz[u]]=min(dper[u][siz[u]],dper[u][lft]+f[i]);
	}
	siz[u]++;
	
	return;
}

int main(){
	memset(dper,0x3f,sizeof(dper));
	
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		scanf("%lld",&f[i]);
	}
	for(int i=1;i<=n-1;i++){
		scanf("%d %d",&ru,&rv);
		so[ru].push_back(rv);
		so[rv].push_back(ru);
	}
	dp(0,1);
	printf("%lld\n",dper[1][n-1]);
	
	return 0;
}