RT，5000的数据范围还跑得不慢评测，用时还没有600ms......求是复杂度分析错了还是数据太水了.....

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int link[5005],to[200005],nex[200005],m=0;
long long dp[5005][5005],f[5005];
//dp[i][j]->i子树保留j个(含i)。
const long long INF=0x7f7f7f7f7f7f7f;
int n;
int sze[5005];
bool vis[5005];
void dfs(int x)
{
	vis[x]=true;
	for (int i=link[x];i>0;i=nex[i])
	{
		if (!vis[to[i]])
		{
			dfs(to[i]);
			sze[x]+=sze[to[i]];
		}
	}
	return ;
}
void solve(int x)
{
	vis[x]=true;
	for (int i=1;i<sze[x];i++) dp[x][i]=INF;
	dp[x][1]=0;
	int mch=0,ns=0;
	//mch->目前纳入考虑子节点数量
	//ns->目前纳入考虑子节点子树和
	//对于目前已纳入考虑的子节点和子树，可知当前节点只能保留1个或者mch+1~ns+1个
	for (int i=link[x];i>0;i=nex[i])
	{
		if (!vis[to[i]])
		{
			solve(to[i]);
			for (int t=ns+1;t>=mch+1;t--)
			{
				for (int c=1;c<=sze[to[i]];c++)
					dp[x][c+t]=min(dp[x][c+t],dp[x][t]+dp[to[i]][c]);
				dp[x][t]=INF;
			}
			//我分析出来这最差是有n^2加上最外面的搜就应该是n^3
			//但5000的范围我过了.......
			mch++;
			ns+=sze[to[i]];
			for (int t=mch;t>=1;t--) dp[x][t]=INF;
		}
	}
	dp[x][1]=f[sze[x]];
	for (int w=mch+1;w<=sze[x];w++)
		dp[x][1]=min(dp[x][1],dp[x][w]+f[w]);
	return ;
}
int main()
{
	int n,u,v;
	scanf("%d",&n);
	for (int i=2;i<=n;i++) scanf("%lld",&f[i]);
	f[1]=0ll;
	memset(link,-1,sizeof(link));
	memset(vis,false,sizeof(vis));
	for (int i=1;i<=n;i++) sze[i]=1;
	for (int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		to[++m]=v;nex[m]=link[u];link[u]=m;
		to[++m]=u;nex[m]=link[v];link[v]=m;
	}
	dfs(1);
	memset(vis,false,sizeof(vis));
	solve(1);
	printf("%lld\n",dp[1][1]);
	return 0;
}