题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1011
题意：
题目大意是有n个房间组成一棵树，你有m个士兵，从1号房间开始让士兵向相邻的房间出发，每个房间里有一个代价，代价是值/20个士兵，
同时有一个价值，问你花费这m个士兵可以得到的最大价值是多少。
思路：
树上背包，这题比较坑爹。士兵为0，输出0。要是一个房间的cost不足20的倍数也要补全20的倍数。
dp[i][j]表示以i节点为子树的root使用j个士兵的最大价值( 不用管父节点 )，dp[i][j] = max(dp[i][j] , dp[i.son][k] + dp[i][j - k])
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = ;
int cost[N], val[N];
vector <int> G[N];
int dp[N][N], n, m; void dfs(int u, int p) {
int temp = (cost[u] + ) / ;
if(temp > m)
return ;
for(int i = temp; i <= m; ++i) {
dp[u][i] = val[u];
}
for(int i = ; i < G[u].size(); ++i) {
int v = G[u][i];
if(v == p)
continue;
dfs(v, u);
for(int j = m; j >= temp + ; --j) { //类似背包 每个可取的值只枚举一次
for(int k = temp; k < j; ++k) { //每条路径上会保证有一个士兵
dp[u][j] = max(dp[u][j], dp[u][k] + dp[v][j - k]);
}
}
}
} int main()
{
while(~scanf("%d %d", &n, &m)) {
if(m == - && n == -)
break;
memset(dp, , sizeof(dp));
for(int i = ; i <= n; ++i) {
G[i].clear();
scanf("%d %d", cost + i, val + i);
}
int u, v;
for(int i = ; i < n; ++i) {
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, -);
if(!m) {
printf("0\n");
} else {
printf("%d\n", dp[][m]);
}
}
return ;
}