题解 P1273 【有线电视网】
这是一个非常不错的树形背包的题目，有助于理解树形背包的实质！ 按照常见树形背包定义状态：设dp[u][j]表示在以u为根的子树中，选择j个客户所能获得的最大收益。
状态转移：dp[u][j]=max(dp[u][j-k],dp[v][k]-w(u,v));
树形背包一直有个疑惑，为什么在枚举背包容量的时候要反向枚举，浅层次的理解就是套用01背包枚举体积；但是细想又不对，因为01背包只有在使用滚动数组的时候才必须逆推；如果使用2维的话不需要；
那是不是意味着树形背包中原本应该是3维，滚动优化为2维了呢？？？
仔细回味01背包的状态定义：f[i][j]表示在前i个物品占用体积为j的空间能够得到的最大价值；这里有一个限定前i个，初次学习树形背包一看人家的代码感觉就是这么写的，并没有深入去思考为什么。
所以仿照01背包定义dp[i][u][j]表示在以u为根的子树的前i棵子树中选择j个节点能够获得的最大费用
dp[i][u][j]=max(dp[i-1][u][j-k]+dp[v的总儿子数][v][k]-w(u,v))
以上就是树形dp没有滚动优化的状态方程，为什么需要滚动优化？为什么可以滚动优化？
为什么需要滚动优化？————不滚动很可能会MLE
为什么可以滚动优化？？？
1.对于u而言很显然是可以滚动优化的，只不过j-k<j要保证dp[u][j-k]是第i-1轮的值则j必须要逆推！！！
2.关键在于v，滚动优化后怎么保证每次dp[v][k]==dp[v的总儿子数][v][k]? 其实关键还是在于01背包的本质的理解，dp[i][v][j]从v的前i个子树中选择j个节点，
递推求解的时候是i依次增大的，所以结束时一定有"i==v的总儿子数" 因此使用滚动数组计算v结束后，dp[v][k]中一定是保存的从v的所有儿子中选k个节点的值；
从而保证dp[v][k]==dp[v的总儿子数][v][k]
#include<bits/stdc++.h>
using namespace std;
const int N=3001;
struct node{
int to,w,nxt;
node(int a=0,int b=0,int c=0):to(a),w(b),nxt(c){}
} g[N];
int fir[N],cnt,money[N],n,m,dp[N][N];
void add(int f,int t,int w){
g[++cnt]=node(t,w,fir[f]);
fir[f]=cnt;
}
int dfs(int u){
if(u>n-m){//u是一个叶子节点
dp[u][1]=money[u];//叶子节点则选一个节点得到最大利益一定是该节点出的钱
dp[u][0]=0;
return 1;
}
dp[u][0]=0;//不选任何节点一定收益为0
int leafs=0;//统计以u为根的子树中叶子的数目
for(int i=fir[u];i;i=g[i].nxt){
int v=g[i].to,w=g[i].w;
int t=dfs(v);//t是v为根的子树中的叶子节点数
leafs+=t;
for(int j=leafs;j>0;j--)//在前i个子树中选，因此这里只需要知道前i个子树的总结点数，而不是u的所有节点个数
for(int k=0,kk=min(j,t);k<=kk;k++)//v最多分到的节点不可能超过他的叶子数，也不能超过其所在子树节点总数
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-w);
}
return leafs;
}
int main(){
int x,t,w;
cin>>n>>m;
for(int i=1;i<=n-m;i++){
cin>>x;
for(int j=0;j<x;j++){
cin>>t>>w;
add(i,t,w);
}
}
for(int j=n-m+1;j<=n;j++)
cin>>money[j];
memset(dp,0x8f,sizeof(dp));
memset(dp,0,sizeof(dp[0]));
dfs(1);
for(int i=m;i>=0;i--){//将用户反向枚举，一旦发现非负数就输出
if(dp[1][i]>=0){
cout<<i<<endl;
break;
}
}
return 0;
}