由电视台，中转站，和用户的电视组成的体系刚好是一棵树
n个节点，编号分别为1~n，1是电视台中心，2~n-m是中转站，n-m+1~n是用户，1为root
现在节点1准备转播一场比赛，已知从一个节点传送数据到达另一个节点，电视台需要一定的费用
若可以传送数据到达用户的节点n-m+1~n，这些用户各自愿意支付一定的费用给电视台
现在电视台希望在不亏本的情况下为尽量多的用户转播比赛
输出最多可以为多少用户转播比赛
背包类型的树形DP第一题
dp[i][j]表示以节点i为根的子树有j个用户获得转播，电视台的最大收益
由于收益有正有负
初始化：
dp[i][0]=0
dp[i][j]=-inf(j>0)
目标：dp[1][j]>=0的条件下最大的j
(dp[1][j]>=0表示电视台不亏本)
dfs的过程递推dp
有个主意的地方写在了注释
#include<cstdio>
#include<cstring> using namespace std; inline int max(int a,int b)
{
return a>b?a:b;
} const int maxn=;
const int inf=0x3f3f3f3f; int dp[maxn][maxn];
int cost[maxn][maxn];
int siz[maxn];
struct Edge
{
int to,next;
};
Edge edge[maxn];
int head[maxn];
int tot;
int n,m; void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
} void init()
{
memset(head,-,sizeof head);
tot=;
for(int i=;i<=n;i++)
{
dp[i][]=;
for(int j=;j<=m;j++)
dp[i][j]=-inf;
}
} void solve();
void dfs(int u); int main()
{
while(~scanf("%d",&n))
{
scanf("%d",&m);
init();
for(int i=;i<=n-m;i++)
{
int num;
scanf("%d",&num);
while(num--)
{
int u;
scanf("%d",&u);
scanf("%d",&cost[i][u]);
addedge(i,u);
}
}
for(int i=n-m+;i<=n;i++)
{
scanf("%d",&cost[i][maxn-]);
}
solve();
}
return ;
} void solve()
{
dfs();
for(int j=siz[];j>=;j--)
{
if(dp[][j]>=)
{
printf("%d\n",j);
return ;
}
}
/*
for(int i=0;i<=siz[1];i++)
printf("%d\n",dp[1][i]);
*/
} void dfs(int u)
{
siz[u]=;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(n-m<v)
{
dp[v][]=;
dp[v][]=cost[v][maxn-];
siz[v]=;
}
else
{
dfs(v);
}
siz[u]+=siz[v]; //由于更新dp[u][j]的时候
//dp[u][j-k]需要表示以u为根的子树，有j-k个是从前面的儿子节点取的
//所以这个时候dp[u][j-k]不可以被儿子节点v更新过（保证j-k个都是从前面取的）
//所以递推时j要逆推
//当然，k和j循环的顺序也就不可以交换了
for(int j=siz[u];j>;j--)
{
for(int k=;k<=siz[v];k++)
if(j>=k)
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-cost[u][v]);
}
}
}