树形背包模板,可以建一个0号节点作为虚拟根节点,把所有节点连接到一个节点上,跑一遍树形背包即可
参考代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=5e4+5;
int n,m;
int w[N],v[N],size[N];
int e[N],h[N],ne[N],idx;
vector<vector<int>>f;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int c)
{
for(int i=h[u];~i;i=ne[i]) //树形背包模板
{
int j=e[i];
for(int k=c+w[j];k<=m;k++) f[j][k]=f[u][k-w[j]]+v[j];
dfs(j,c+w[j]);
for(int k=c+w[j];k<=m;k++) f[u][k]=max(f[u][k],f[j][k]);
}
}
int main()
{
cin>>n>>m;
f.resize(n+1);
for(int i=0;i<=n;i++)
{
f[i].resize(m+1);
}
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
if(a) add(a,i);
else add(0,i);
}
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) cin>>v[i];
dfs(0,0);
cout<<f[0][m]<<'\n';
return 0;
}
感觉不会的还是会看不懂(>_/<)
qwq,这是校赛,大家可以在群里面交流.