Problem Description
You, the leader of Starship Troopers, are sent to destroy a base of the bugs. The base is built underground. It is actually a huge cavern, which consists of many rooms connected with tunnels. Each room is occupied by some bugs, and
their brains hide in some of the rooms. Scientists have just developed a new weapon and want to experiment it on some brains. Your task is to destroy the whole base, and capture as many brains as possible. To kill all the bugs is always easier than to capture
their brains. A map is drawn for you, with all the rooms marked by the amount of bugs inside, and the possibility of containing a brain. The cavern's structure is like a tree in such a way that there is one unique path leading to each room from the entrance.
To finish the battle as soon as possible, you do not want to wait for the troopers to clear a room before advancing to the next one, instead you have to leave some troopers at each room passed to fight all the bugs inside. The troopers never re-enter a room
where they have visited before. A starship trooper can fight against 20 bugs. Since you do not have enough troopers, you can only take some of the rooms and let the nerve gas do the rest of the job. At the mean time, you should maximize the possibility of
capturing a brain. To simplify the problem, just maximize the sum of all the possibilities of containing brains for the taken rooms. Making such a plan is a difficult job. You need the help of a computer.
their brains hide in some of the rooms. Scientists have just developed a new weapon and want to experiment it on some brains. Your task is to destroy the whole base, and capture as many brains as possible. To kill all the bugs is always easier than to capture
their brains. A map is drawn for you, with all the rooms marked by the amount of bugs inside, and the possibility of containing a brain. The cavern's structure is like a tree in such a way that there is one unique path leading to each room from the entrance.
To finish the battle as soon as possible, you do not want to wait for the troopers to clear a room before advancing to the next one, instead you have to leave some troopers at each room passed to fight all the bugs inside. The troopers never re-enter a room
where they have visited before. A starship trooper can fight against 20 bugs. Since you do not have enough troopers, you can only take some of the rooms and let the nerve gas do the rest of the job. At the mean time, you should maximize the possibility of
capturing a brain. To simplify the problem, just maximize the sum of all the possibilities of containing brains for the taken rooms. Making such a plan is a difficult job. You need the help of a computer.
Input
The input contains several test cases. The first line of each test case contains two integers N (0 < N <= 100) and M (0 <= M <= 100), which are the number of rooms in the cavern and the number of starship troopers you have, respectively.
The following N lines give the description of the rooms. Each line contains two non-negative integers -- the amount of bugs inside and the possibility of containing a brain, respectively. The next N - 1 lines give the description of tunnels. Each tunnel is
described by two integers, which are the indices of the two rooms it connects. Rooms are numbered from 1 and room 1 is the entrance to the cavern. The last test case is followed by two -1's.
The following N lines give the description of the rooms. Each line contains two non-negative integers -- the amount of bugs inside and the possibility of containing a brain, respectively. The next N - 1 lines give the description of tunnels. Each tunnel is
described by two integers, which are the indices of the two rooms it connects. Rooms are numbered from 1 and room 1 is the entrance to the cavern. The last test case is followed by two -1's.
Output
For each test case, print on a single line the maximum sum of all the possibilities of containing brains for the taken rooms.
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
题目意思：有N 个洞，到达每个洞只有一条路可通，形成一棵树状，每个洞里面有虫守着一定价值东西，现在用M 个士兵去占领洞，只有占了该洞才能得到该洞里的东西，己知每个士兵可以消灭20个虫；只有占了一个洞才能继续前进，否则无法走到子树上的洞；1为入口洞。求M个士兵能得到的最大价值。
这是做的第一道树形DP，看了网上的才解出。 本人的体会就是：必须明白dp每一维数代表的是什么意思，才能解出。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define P 105
#define M 105
struct tree
{
int k;
int child[105];
}node[105];
int dp[P][M];//用M个骑士去占领以P为根的树，得到的最大价值
int trooperNum,vist[105],useTroop[105],brain[105];
void dfs(int p)
{
vist[p]=1;
for(int u=useTroop[p];u<=trooperNum;u++)//只有先占了树根p，才可以去占子树
dp[p][u]=brain[p];
for(int k=1;k<=node[p].k;k++)
{
int chil=node[p].child[k];//p的子节点
if(vist[chil]) continue;//访问过了就不能重复走，这就是区分根节点与子节点
dfs(chil);
//子树的最大价值只能加一次，反以用01背包的思想从大到小
for(int num=trooperNum;num>=useTroop[p];num--)//用num个骑士占领以p为根的树（有的子树可以不占），更新最大值
for(int chilU=1;chilU<=num-useTroop[p];chilU++)//用chilU个骑士去占领以chil点为根的树，在更新中可占可不占
if(dp[p][num]<dp[p][num-chilU]+dp[chil][chilU])//注意加的是用chilU个骑士占领的以chil点为根的子树的最大值
dp[p][num]=dp[p][num-chilU]+dp[chil][chilU];
}
}
int main()
{
int N,a,b,k;
while(scanf("%d%d",&N,&trooperNum)>0)
{
if(N==trooperNum&&N==-1)
break;
for(int i=1;i<=N;i++)
{
scanf("%d%d",&useTroop[i],&brain[i]);
useTroop[i]=(useTroop[i]+19)/20;
node[i].k=0;
}
for(int i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
node[a].k++; k=node[a].k; node[a].child[k]=b;
node[b].k++; k=node[b].k; node[b].child[k]=a;
}
if(trooperNum==0)//注意这里，在实际中没有人去那么就不可能得到东西
{
printf("0\n"); continue;
}
memset(dp,0,sizeof(dp));
memset(vist,0,sizeof(vist));
dfs(1);
printf("%d\n",dp[1][trooperNum]);
}
}