[数据](https://www.luogu.org/paste/0ba04iss)
by 7KByte @ 2019-07-17 18:00:57
@[Gang_Leader](/space/show?uid=119261) 按照某一种方式转移的树形背包的复杂度是正确的 $O(n^2)$ 。
by hsfzLZH1 @ 2019-07-17 18:08:02
@[hsfzLZH1](/space/show?uid=43486) 但事实上这些树形背包都没有跑过上面那组数据啊
by 7KByte @ 2019-07-17 18:10:42
https://blog.csdn.net/qkoqhh/article/details/82659832
by hsfzLZH1 @ 2019-07-17 18:16:21
正确的输出是 1500 吗
by hsfzLZH1 @ 2019-07-17 18:38:37
数据生成器出锅了，此贴完结
by hsfzLZH1 @ 2019-07-18 11:44:32
@[Inf_Voltage](/user/119261) 我这里有个n^2的方法，就是还是像原来一样设置状态但是可以向下的时候把子树状态看成父亲及父亲之前子树的状态
```cpp
#include<bits/stdc++.h>
using namespace std;
int read()
{
char c;
int w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
int ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
int f[3005][3005];
int n,m;
struct node
{
int next,to,v;
}e[100005];
int cnt;
int h[3005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].next=h[x];
h[x]=cnt;
e[cnt].to=y;
e[cnt].v=z;
}
int c[10005];
void dfs(int x)
{
int vis=1;
f[x][0]=0;
for(int i=h[x];i;i=e[i].next)
{
vis=0;
for(int y=1;y<=m;y++)
{
f[e[i].to][y]=f[x][y];
}
dfs(e[i].to);
for(int y=1;y<=m;y++)
{
f[x][y]=max(f[x][y],f[e[i].to][y]-e[i].v);
}
}
if(vis)
{
for(int i=m;i>=1;i--)
f[x][i]=max(f[x][i],f[x][i-1]+c[x]);
}
// for(int i=0;i<=m;i++)
// cout<<x<<" "<<i<<" "<<f[x][i]<<endl;
return ;
}
int main(){
memset(f,-0x3f,sizeof(f));
n=read();
m=read();
for(int i=1;i<=n-m;i++)
{
int k=read();
while(k--)
{
int a,b;
b=read();
a=read();
add(i,b,a);
}
}
for(int i=1;i<=m;i++)c[n-m+i]=read();
dfs(1);
int res=0;
for(int i=0;i<=m;i++)
{
// cout<<f[1][i]<<endl;
if(f[1][i]>=0)res=max(res,i);
}
cout<<res<<endl;
return 0;
}
```
by 一念之间、、 @ 2020-10-04 10:13:05
@[Inf_Voltage](/user/119261) 您的那个数据不见了，您可以试试我的这个代码能不能跑过，这是n^2的
by 一念之间、、 @ 2020-10-04 10:13:54