Hihocoder 1055

题意：求连通的m个节点最大权值和。
dp过程类似背包问题，不用单独的求解每一个f(t, m)而是针对于每一个t，同时求解它的f(t, 0..M)。
自己思考的话比较难， 现在也没有彻底理解， 为什么这样就可以满足连通的要求。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

bool Sqrt(LL n) { return (LL)sqrt(n) * sqrt(n) == n; }
const double PI = acos(-1.0), ESP = 1e-10;
const LL INF = 99999999999999;
const int inf = 999999999;
int n, m, a, b;
vector<vector<int> > G, dp;
void dfs(int u, int p)
{
	for(auto e : G[u]) {
		if(e != p) {
			dfs(e, u);
			for(int i = m; i >= 2; i--)
				for(int j = 1; j < i; j++)
					dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[e][j]);
		}
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	while(~scanf("%d%d", &n, &m)) {
		G.assign(n + 1, vector<int>());
		dp.assign(n + 1, vector<int>(m+1, 0));
		for(int i = 1; i <= n; i++) scanf("%d", &dp[i][1]);
		for(int i = 0; i < n - 1; i++) {
			scanf("%d%d", &a, &b);
			G[a].push_back(b); G[b].push_back(a);
		}
		dfs(1, 0);
		printf("%d
", dp[1][m]);
	}

	return 0;
}
/*
    input:
    output:
    modeling:
    methods:
    complexity:
    summary:
*/