Description：
你作为星际舰队舰长被派去摧毁虫族基地。基地实际上是一个巨大的洞穴，由许多空间与隧道相连。每个空间都有一些虫子，虫群之心藏在一些空间里。你的任务是摧毁整个基地，并捕获尽可能多的虫群之心。你获得一张地图，所有的空间都标有里面虫子的数量，还有可能有一个虫群之心。洞穴结构是一棵树，从入口到每个空间都有一条小路。为了尽快完成战斗，你必须在经过的每个空间留下一些舰船来对付里面的所有虫子。舰队再也不会进入以前去过的空间。
一艘舰船可以对付20只虫子。舰船不够，只能占领一些空间，剩下的交给神经毒气（这个空间的虫群之心也会死去），同时最大化捕捉虫群之心的可能性。即只要最大限度地将占用空间的虫群之心的所有可能性加起来。
Sample Input 5 10 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5 1 1 20 7 -1 -1 Sample Output 50 7
我们用dp[i][j]来表示当前第i个空间中派了j个舰船去获得虫群之心的概率，dp[v][k]表示当前第v个空间中派了k个舰船去获得虫群之心的概率,,v为u的一个子空间从而可以得到状态转移方程：
dp[i][j] = max(dp[i][j], dp[i][j-k] + dp[v][k])，总概率 f = ∑ max(dp[i][j], dp[i][j-k] + dp[v][k]) （j<k）
转移的过程结合了树形DP和背包DP的特点，我们枚举i的每个子节点v，并分别在i和v分派j - k和k搜舰船的概率，代码如下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAXN 100+10
using namespace std;
vector<int> G[MAXN];//地图
int dp[MAXN][MAXN];//dp[i][j]表示在空间i时 用过j个飞船 得到的抓获头目的最大概率
int val[MAXN];//每个空间能抓获头目的概率值
int num[MAXN];//记录每个空间 消耗的舰船数目
int N, M;
void DFS(int u, int fa)
{
for(int i = num[u]; i <= M; i++)//预处理
dp[u][i] = val[u];
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(v == fa) continue;
DFS(v, u);
//0-1 背包 求使用M个舰船 所能得到的抓获头目的最大概率
for(int j = M; j >= num[u]; j--)
{
for(int k = 1; k + num[u] <= j; k++)//枚举 到v空间时 可能消耗的舰船数目
{
if(dp[v][k])
dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
}
}
}
}
int main()
{
while(scanf("%d%d", &N, &M), N!=-1||M!=-1)
{
int a, b;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= N; i++)
{
G[i].clear();
scanf("%d%d", &num[i], &val[i]);
if(num[i] % 20 == 0)//求出每个洞穴需要舰船的数目
num[i] /= 20;
else
num[i] = num[i] / 20 + 1;
}
for(int i = 1; i < N; i++)
{
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
if(M == 0)//单独判断
{
printf("0
");
continue;
}
DFS(1, -1);
printf("%d
", dp[1][M]);
}
return 0;
}