题解 P1273 【有线电视网】
树形dp（分组背包）
蒟蒻因为看不懂题解自己写结果一次ac的故事
说一下自己的理解
1.明确dp[i][j]含义，表示i节点，选j个用户，能得到的钱的最大值，然后对每个节点做分组背包。
2.怎么看出是分组背包？首先，背包的总容量相当于该点为根节点的子树中所有的用户数量（dp[i][j]的 j 不可能超过它连接的所有用户数）。然后，把该节点的每个儿子看成一组，每组中的元素为选一个，选两个...选n个用户。
3.转移方程 dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-这条边的花费) i,j不解释了，v表示枚举到这一组（即i的儿子），k表示枚举到这组中的元素：选k个用户。
4.最后输出dp[1][i]>=0的i的最大值，所以反向枚举。
代码丑
更新一下
说一下分组背包吧qwq
分组背包：若干组物品，每组中的物品互相冲突（就是说每组中最多只能选一件物品），求最大价值
伪代码如下
for(int k=1;k<=总共的组数;k++)//遍历所有的组k
for(int j=v;j>=1;j--)//跟01背包类似，倒序枚举背包容量
for(int i=1;i<=组中的元素个数;i++)//遍历这组中所有的元素仔细看的话和树形dp的代码是一模一样的呢
再解释一下这道题的思路
简单来说就是把每个节点看成一个背包啦，它的容量就是以这个节点为根的子树大小，组数就是连接的儿子个数。
每组都有很多选择，选一个，两个，三个用户，把这些选择当做组中的元素就好了，容易看出每组中只能选一个元素，比如你选择了选一个用户，就不可能同时选择选两个用户。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;//n为整个有线电视网的结点总数，m为用户终端的数量
//第一个转播站即树的根结点编号为1，其他的转播站编号为2到n-m，用户终端编号为n-m+1到n
int head[3010],k;
int val[3010];//用户为观看比赛而准备支付的钱数
int dp[3010][3010];//dp[i][j]表示i节点，选j个用户，能得到的钱的最大值
struct node
{
int to,next,w;
}edge[10000010];
void adde(int u,int v,int w)
{
edge[++k].to=v; edge[k].next=head[u];
edge[k].w=w; head[u]=k;
}
int dfs(int u)
{
if(u>n-m)//u为用户终端
{
dp[u][1]=val[u];
return 1;
}
int sum=0,t;
for(int k=head[u];k;k=edge[k].next)//该点连接了几个节点意为有几组，遍历每一组
{
int v=edge[k].to;
t=dfs(v); sum+=t; //t为该组的元素个数，或是说这个儿子为根的子树大小（这里的大小指子树中用户的个数），sum为该节点最多可以选多少个用户，即背包容量
for(int j=sum;j>0;j--)
{
for(int i=1;i<=t;i++)//遍历组中的元素，选多少个用户相当于一个元素
{
if(j-i>=0) dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]-edge[k].w);
}
}
}
return sum;
}
int main()
{
memset(dp,~0x3f,sizeof(dp));//初始化一个极大负值，因为dp可能为负
scanf("%d%d",&n,&m);
for(int u=1;u<=n-m;u++)
{
int size,v,w;
scanf("%d",&size);
for(int j=1;j<=size;j++)
{
scanf("%d%d",&v,&w);
adde(u,v,w);
}
}
for(int i=n-m+1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<=n;i++) dp[i][0]=0;//选0个用户的花费肯定是0啦
dfs(1);
for (int i=m;i>=1;i--)
if (dp[1][i]>=0)
{
printf("%d",i);
break;
}
return 0;
}