学步园

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<memory.h>
#include<time.h>

using namespace std;

#define inf 200000000

long long dp[109][109],ans,w[109];
int head[109],cnt,n,k;

struct Node
{
	long long from,to;
}node[500];

void clear()
{
	memset(node,0,sizeof(node));
	memset(head,-1,sizeof(head));
	memset(dp,0,sizeof(dp));
	cnt=0;
}

void add(int a,int b)
{
	node[cnt].from=b;
	node[cnt].to=head[a];
	head[a]=cnt++;
	ans=-inf;
}

void dfs(int u,int fa)
{
	for(int i=0;i<=k;++i)
		dp[u][i]=-inf;
	dp[u][1]=w[u];
	for(int j=head[u];j!=-1;j=node[j].to)
	{
		int v=node[j].from;
		if(v!=fa)
		{
			dfs(v,u);
			for(int l=k;l>=1;--l)
			{
				for(int i=k;i>=1;--i)
				{
					if(dp[v][i]==-inf)continue;
					if(l+i>k || dp[u][l]==-inf)continue;
					dp[u][l+i]=max(dp[v][i]+dp[u][l],dp[u][l+i]);
				}
			}
		}
	}
	ans=max(ans,dp[u][k]);
}

int main()
{
	while(scanf("%d %d",&n,&k)!=EOF)
	{
		clear();
		for(int i=0;i<n;++i)
			scanf("%lld",&w[i]);
		for(int i=1;i<n;++i)
		{
			int a,b;
			scanf("%d %d",&a,&b);
			add(a,b);
			add(b,a);
		}
		dfs(0,-1);
		cout<<ans<<endl;
	}
	return 0;
}