#include #include #include #include #include using namespace std; int n,m,a[10000001],s[10000001],dp[505][505],f[505][505],upd[505],upf[505]; int head[10000001],ne[10000001],to[10000001],id; void add(int x,int y){ to[++id]=y,ne[id]=head[x],head[x]=id; to[++id]=x,ne[id]=head[y],head[y]=id; } void dfs(int u,int fa){ dp[u][0]=f[u][0]=0; dp[u][1]=f[u][1]=a[u]; for(int i=head[u];i;i=ne[i]){ int v=to[i]; if(v==fa) continue; dfs(v,u); for(int j=m;j>=1;j--){ f[u][j]=max(f[u][j],f[v][j-1]); for(int k=j-2;k>=0;k--){ dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-2]); f[u][j]=max(f[u][j],f[v][k]+dp[u][j-k-1]); f[u][j]=max(f[u][j],dp[v][k]+f[u][j-k-2]); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1,u,v;i<n;i++){ cin>>u>>v; add(u,v); } dfs(1,0); int ans=0; for(int i=1;i<=m;i++){ ans=max(ans,f[1][i]); } cout<<ans; }