学步园

树形DP：

AC代码如下：

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

int N, M;
int w[101], v[101];
vector<int> gra[101];
bool visit[101];
int dp[101][101];

inline int max( int a, int b ){
	return ( a > b ? a : b );
}

void DFS( int n ){
	for( int i = M; i >= w[n]; i-- ){
		dp[n][i] = v[n];
	}
	visit[n] = true;
	for( int i = 0; i < gra[n].size(); i++ ){
		int t = gra[n][i];
		if( visit[t] ){
			continue;
		}
		DFS( t );
		for( int j = M; j >= w[n]; j-- ){
			for( int k = 1; k <= j - w[n]; k++ ){//要留下w[n]的士兵来攻打n
				dp[n][j] = max( dp[n][j], dp[n][j-k] + dp[t][k] );
			}
		}
	}
}

int main(){
	while( cin >> N >> M && !( N == -1 && M == -1 ) ){
		memset( visit, false, sizeof( visit ) );
		memset( dp, 0, sizeof( dp ) );
		for( int i = 0; i <= 100; i++ ){
			gra[i].clear();
		}
		for( int i = 1; i <= N; i++ ){
			cin >> w[i] >> v[i];
			w[i] = ( w[i] + 19 ) / 20;
		}
		for( int i = 1; i < N; i++ ){
			int temp1, temp2;
			cin >> temp1 >> temp2;
			gra[temp1].push_back( temp2 );
			gra[temp2].push_back( temp1 );
		}
		if( M == 0 ){
			cout << 0 << endl;
			continue;
		}
		DFS( 1 );
		cout << dp[1][M] << endl;
	}
	return 0;
}