题目链接：https://vjudge.net/problem/HDU-1011
题意：给定一颗树，每个结点有两个属性，即花费V和价值w，并且选择子结点时必须选择父结点，求总花费不超过m的最大价值。
思路：
树上分组背包。和poj1155相似，对于结点u，先递归计算其子结点v的dp值，然后对于每个子结点所代表的子树，最多只有一种选择方案，不能重叠，所以是分组背包。dp[u][j]表示对结点u表示的子树，容量为j时的最大价值。dfs时的num表示从根节点到u的花费(including u)，计算结点u时，枚举容量从大到小，容量最大为m-num。
我是先讨论选择u的子结点的情况，最后讨论选不选u，容量从大到小遍历，最大为m-num+V[u]，注意和前面的m-num不同（前面的实际上是u的子结点的最大容量，此处的才是u代表的子树的最大容量）。
AC代码：
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn=;
int n,m,cnt,head[maxn],V[maxn],w[maxn],dp[maxn][maxn];
struct node{
int v,nex;
}edge[maxn<<]; void adde(int u,int v){
edge[++cnt].v=v;
edge[cnt].nex=head[u];
head[u]=cnt;
} void dfs(int u,int fa,int num){
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].v;
if(v==fa) continue;
dfs(v,u,num+V[v]);
for(int j=m-num;j>;--j)
for(int k=;k<=j;++k)
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
for(int j=m-num+V[u];j>;--j)
if(j>=V[u]) dp[u][j]=dp[u][j-V[u]]+w[u];
else dp[u][j]=;
} int main(){
while(scanf("%d%d",&n,&m),n>=&&m>=){
cnt=;
for(int i=;i<=n;++i){
head[i]=;
for(int j=;j<=m;++j)
dp[i][j]=;
}
for(int i=;i<=n;++i){
scanf("%d%d",&V[i],&w[i]);
V[i]=(V[i]+)/;
}
for(int i=;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
dfs(,,V[]);
printf("%d\n",dp[][m]);
}
return ;
}