poj-2486-Apple Tree

// poj-2486  

#include <cstdio> 
#include <cstring> 


#include <iostream> 
#include <vector> 
using namespace std; 

const int MAXN = 100 + 10; 

int n, k, val[MAXN], vis[MAXN], dp[MAXN][2*MAXN][2]; 

vector<int> vt[MAXN]; 

void dfs(int x){
	vis[ x ] = 1;  
	for(int i=0; i<vt[x].size(); ++i){
		int y = vt[x][i]; 
		if(vis[ y ] == 1){
			continue; 
		} 
		dfs(y); 
		for(int j=k; j>=1; --j){
			for(int t=1; t<=j; ++t){
				dp[x][j][0] = max( dp[x][j][0], dp[x][j-t][1] + dp[y][t-1][0] ); 
				if(t >= 2){
					dp[x][j][0] = max(dp[x][j][0], dp[x][j-t][0] + dp[y][t-2][1] ); 
					dp[x][j][1] = max(dp[x][j][1], dp[x][j-t][1] + dp[y][t-2][1] ); 
				}
			}
		} 
	}
}

int main(){
	freopen("in.txt", "r", stdin); 

	int a, b, ans;  
	while(scanf("%d %d", &n, &k) != EOF){
		memset(dp, 0, sizeof(dp)); 
		memset(vis, 0, sizeof(vis)); 

		for(int i=1; i<=n; ++i){
			scanf("%d", &val[i]); 

			for(int j=0; j<=k; ++j){
				dp[i][j][0] = dp[i][j][1] = val[i]; 
			}
		}

		for(int i=1; i<=n; ++i){
			vt[i].clear(); 
		}

		for(int i=1; i<n; ++i){
			scanf("%d %d", &a, &b); 
			vt[a].push_back(b); 
			vt[b].push_back(a); 
		} 

		dfs(1); 

		ans = max(dp[1][k][0], dp[1][k][1]); 

		printf("%d\n", ans );
	} 
	return 0; 
}