问题：你，星舰士兵的首领，被派去摧毁一个虫子基地。基地建在地下。它实际上是一个巨大的洞穴，由许多与隧道相连的房间组成。每个房间都被一些虫子占据，它们的大脑藏在一些房间里。科学家们刚刚开发了一种新武器，想在一些大脑上进行实验。你的任务是摧毁整个基地，并捕获尽可能多的大脑。
杀死所有的虫子总是比捕捉它们的大脑容易。一张地图为你绘制，所有的房间都标有里面虫子的数量，以及包含大脑的可能性。洞穴的结构就像一棵树，从入口到每个房间都有一条独特的路径。为了尽快结束战斗，你不想等士兵们清理完一个房间再前进到下一个房间，而是必须在每个经过的房间留下一些士兵来对抗里面的所有虫子。士兵们永远不会再进入他们以前去过的房间。
一个星际飞船士兵可以对抗 20 个虫子。由于你没有足够的士兵，你只能拿走一些房间，让神经毒气来做剩下的工作。与此同时，你应该最大限度地抓住大脑的可能性。为了简化问题，只要最大化被占领房间包含大脑的所有可能性的总和。制定这样的计划是一项艰巨的工作。你需要电脑的帮助。
输入输入：
包含几个测试用例。每个测试用例的第一行包含两个整数 N（0<N<=100）和 M（0<=M<=100），分别是洞穴中的房间数量和您拥有的星际飞船士兵数量。以下 N 行给出了房间的描述。每行包含两个非负整数 —— 分别是里面的虫子数量和包含大脑的可能性。接下来的 N-1 行给出了隧道的描述。每个隧道由两个整数描述，这是它连接的两个房间的索引。房间从 1 开始编号，房间 1 是洞穴的入口。
最后一个测试用例后面跟着两个 - 1。
输出对于每个测试用例，在单行上打印所取房间包含大脑的所有可能性的最大总和。
示例输入：
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
输出：50 7
代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
#define MAX_M 100
typedef struct {
int bugs;
int possibility;
} Room;
typedef struct {
int *adjacent;
int size;
} AdjList;
int dfs(int node, int soldiers, Room *rooms, AdjList *graph, int *dp, int parent) {
if (dp[node * MAX_M + soldiers]!= -1) {
return dp[node * MAX_M + soldiers];
}
int possibility = 0;
if (soldiers >= rooms[node].bugs / 20) {
possibility = rooms[node].possibility;
}
int maxPossibility = possibility;
for (int i = 0; i < graph[node].size; i++) {
int neighbor = graph[node].adjacent[i];
if (neighbor!= parent) {
int newSoldiers = soldiers - (rooms[node].bugs / 20);
int childPossibility = dfs(neighbor, newSoldiers, rooms, graph, dp, node);
maxPossibility = (maxPossibility > possibility + childPossibility)? maxPossibility : (possibility + childPossibility);
}
}
dp[node * MAX_M + soldiers] = maxPossibility;
return maxPossibility;
}
int main() {
int n, m;
while (scanf("%d %d", &n, &m)!= EOF && n!= -1 && m!= -1) {
Room rooms[MAX_N];
AdjList graph[MAX_N];
int dp[MAX_N * MAX_M];
for (int i = 0; i < n; i++) {
graph[i].adjacent = (int *)malloc(sizeof(int) * n);
graph[i].size = 0;
}
for (int i = 0; i < n; i++) {
scanf("%d %d", &rooms[i].bugs, &rooms[i].possibility);
}
for (int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[a - 1].adjacent[graph[a - 1].size++] = b - 1;
graph[b - 1].adjacent[graph[b - 1].size++] = a - 1;
}
for (int i = 0; i < n * MAX_M; i++) {
dp[i] = -1;
}
int maxPossibility = dfs(0, m, rooms, graph, dp, -1);
printf("%d\n", maxPossibility);
for (int i = 0; i < n; i++) {
free(graph[i].adjacent);
}
}
return 0;
}
