记录编号	141952	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]切割	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-12-05 17:03:03	内存使用	1.96 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=60;
double MX=0;
int N,K1,K2;
vector<int> c[SIZEN];
double val[SIZEN]={0};
double f[SIZEN][SIZEN][SIZEN]={0},g[SIZEN]={0};
int fa[SIZEN]={0};
void DP(int x){
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(u!=fa[x]){
			fa[u]=x;
			DP(u);
		}
	}
	g[x]=MX;
	for(int j=K1;j<=K2;j++){
		for(int i=1;i<=N;i++) f[x][j][i]=MX;
		f[x][j][1]=val[x]/(j+0.0);
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i];
			if(u==fa[x]) continue;
			for(int k=j;k>=1;k--){
				f[x][j][k]+=g[u];
				for(int l=1;l<k;l++)
					f[x][j][k]=min(f[x][j][k],f[x][j][k-l]+f[u][j][l]);
			}
		}
		g[x]=min(g[x],f[x][j][j]);
	}
}
void read(void){
	scanf("%d%d%d",&N,&K1,&K2);
	for(int i=1;i<=N;i++){
		scanf("%lf",&val[i]);
		MX+=2*val[i];
	}
	int x,y;
	for(int i=1;i<N;i++){
		scanf("%d%d",&x,&y);
		c[x].push_back(y);
		c[y].push_back(x);
	}
}
int main(){
	freopen("nt2011_cut.in","r",stdin);
	freopen("nt2011_cut.out","w",stdout);
	read();
	DP(1);
	printf("%.2lf\n",g[1]);
	return 0;
}