```
#include<cstdio>
#define max(a,b)((a)<(b)?(b):(a))
const int N=3e3+3;
int head[N],nxt[N],cnt,to[N],dis[N];
inline void addedge(int _from,int _to,int dist)
{
nxt[++cnt]=head[_from];
head[_from]=cnt;
to[cnt]=_to;
dis[cnt]=dist;
}
int dp[N][N],l[N],n,m,w[N];
void dfs(int now)
{
register int i,j,k;
for(i=head[now];i;i=nxt[i])
{
dfs(to[i]);
l[now]+=l[to[i]];
for(j=1;j<=l[to[i]];j++)
for(k=l[now];k>=j;k--)
dp[now][k]=max(dp[now][k],dp[now][k-j]+dp[to[i]][j]-dis[i]);
}
}
int main()
{
scanf("%d %d",&n,&m);
register int i,j;
for(i=1;i<=n-m;i++)
{
int totson;
scanf("%d",&totson);
while(totson--)
{
int node,dist;
scanf("%d %d",&node,&dist);
addedge(i,node,dist);
}
}
for(;i<=n;i++)
{
scanf("%d",w+i);
dp[i][1]=w[i];
l[i]=1;
}
for(i=1;i<=n-m;i++)
for(j=1;j<=m;j++)
dp[i][j]=-1e9;
dfs(1);
for(i=l[1];;i--)
if(dp[1][i]>=0) return printf("%d\n",i)&0;
}
```
by shuyingte @ 2019-04-07 18:33:56
```
#include<cstdio>
#define max(a,b)((a)<(b)?(b):(a))
const int N=3e3+3;
int head[N],nxt[N],cnt,to[N],dis[N];
inline void addedge(int _from,int _to,int dist)
{
nxt[++cnt]=head[_from];
head[_from]=cnt;
to[cnt]=_to;
dis[cnt]=dist;
}
int dp[N][N],l[N],n,m,w[N];
void dfs(int now)
{
register int i,j,k;
for(i=head[now];i;i=nxt[i])
{
dfs(to[i]);
l[now]+=l[to[i]];
for(k=l[now];~k;k--)
for(j=1;j<=l[to[i]];j++)
if(k>=j)dp[now][k]=max(dp[now][k],dp[now][k-j]+dp[to[i]][j]-dis[i]);
}
}
int main()
{
scanf("%d %d",&n,&m);
register int i,j;
for(i=1;i<=n-m;i++)
{
int totson;
scanf("%d",&totson);
while(totson--)
{
int node,dist;
scanf("%d %d",&node,&dist);
addedge(i,node,dist);
}
}
for(;i<=n;i++)
{
scanf("%d",w+i);
dp[i][1]=w[i];
l[i]=1;
}
for(i=1;i<=n-m;i++)
for(j=1;j<=m;j++)
dp[i][j]=-1e9;
dfs(1);
for(i=l[1];;i--)
if(dp[1][i]>=0) return printf("%d\n",i)&0;
}
```
by shuyingte @ 2019-04-07 18:34:23
~~然后我为了检验真理而提交。过两天棕名，因为抄题解~~
by _Misaka_Mikoto @ 2019-04-07 18:35:17
@[Xeon](/space/show?uid=138904) ~~现在很少查了吧~~
by Yoo_ @ 2019-04-07 18:36:05
@[我的智商贼低](/space/show?uid=114677) 最近棕名的也不少
by _Misaka_Mikoto @ 2019-04-07 18:37:53
试一遍就知道了
by D447H @ 2019-08-23 14:28:38