记录编号	152019	评测结果	AAAAAAAAAA
题目名称	寻宝之旅	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-03-12 18:30:52	内存使用	0.40 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct Trangles{
   int p[5];
   bool operator <(const Trangles &rhs) const{
      if (p[1]!=rhs.p[1]) return p[1]<rhs.p[1];
      if (p[2]!=rhs.p[2]) return p[2]<rhs.p[2];
      if (p[3]!=rhs.p[3]) return p[3]<rhs.p[3];
      return false;
   }
   void Make(){
      int &a=p[1],&b=p[2],&c=p[3];
      if (a>b) swap(a,b);
      if (b>c) swap(b,c);
      if (a>b) swap(a,b);
   }
};
///==============var declaration=================
const int MAXN=150;
int n,m;
int val[MAXN],f[MAXN][MAXN];//在I节点时还有J个人能够获得的最大收益
int rem[MAXN];
vector <int> Edge[MAXN];
///==============function declaration============
void dp(int x,int pa);
///==============main code=======================
int main()
{
   freopen("seek.in","r",stdin);
   freopen("seek.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)   scanf("%d",val+i);
   for(int i=1;i<n;i++){
      int s,e;scanf("%d%d",&s,&e);
      Edge[s].push_back(e);Edge[e].push_back(s);
   }
   dp(1,-1);
   printf("%d\n",f[1][m]);
   return 0;
}
///================fuction code====================
void dp(int x,int pa){
   int siz=Edge[x].size();
   for(int i=0;i<siz;i++){
      int &e=Edge[x][i];
      if (e==pa) continue;
      dp(e,x);
   }
   memcpy(rem,f[x],sizeof (rem));
   for(int i=0;i<siz;i++){
      if (Edge[x][i]==pa)  continue;
      for(int j=1;j<=m;j++)
         f[x][j]=max(f[Edge[x][i]][j],f[x][j]);///什么都不做，所有人下去
   }
   for(int i=0;i<siz;i++){
      if (Edge[x][i]==pa) continue;
      for(int j=m;j>=1;j--)
        for(int cost=1;cost<=j;cost++)
            rem[j]=max(rem[j],rem[j-cost]+f[Edge[x][i]][cost]);
   }
   for(int j=m;j>=1;j--) rem[j]=rem[j-1];
   rem[1]=0;
   for(int i=1;i<=m;i++)
      f[x][i]=max(f[x][i],rem[i]+val[x]);
}