s;inline void add(int uu,int vv){++tot_e;edge[tot_e].u=uu;edge[tot_e].v=vv;edge[tot_e].nxt=first[uu];first[uu]=tot_e;}inline void add2(int uu,int vv){++tot_e2;edge2[tot_e2].u=uu;edge2[tot_e2].v=vv;edge2[tot_e2].nxt=first2[uu];first2[uu]=tot_e2;}inline void tarjan(int x){dfn[x]=low[x]=++cnt;s.push(x);instack[x]=true;for(rint i=first[x];i;i=edge[i].nxt){int y=edge[i].v;if(!dfn[y]){tarjan(y);low[x]=min(low[y],low[x]);}else if(instack[y])low[x]=min(dfn[y],low[x]);}if(dfn[x]==low[x]){++tot_q;while(1){int lin=s.top();s.pop();instack[lin]=false;belong[lin]=tot_q;qw[tot_q]+=w[lin];qv[tot_q]+=v[lin];if(lin==x) break;}}}inline void dfs(int x){for(rint i=first2[x];i;i=edge2[i].nxt){int to=edge2[i].v;dfs(to);for(rint j=m;j>=0;--j){for(rint p=0;p<=j;++p)dp[x][j]=max(dp[x][j],dp[to][p]+dp[x][j-p]);}}for(rint i=m;i>=0;--i){if(i>=qw[x]) dp[x][i]=dp[x][i-qw[x]]+qv[x];else dp[x][i]=0;}}int main(){scanf("%d %d",&n,&m);for(rint i=1;i<=n;++i)scanf("%d",&w[i]);for(rint i=1;i<=n;++i)scanf("%d",&v[i]);for(rint i=1;i<=n;++i){scanf("%d",&d[i]);if(d[i]) add(d[i],i);}for(rint i=1;i<=n;++i)if(!dfn[i])tarjan(i);for(rint i=1;i<=n;++i){if(!d[i]) continue;if(belong[i]==belong[d[i]]) continue;add2(belong[d[i]],belong[i]);deg[belong[i]]++;}/*for(rint x=1;x<=n;x++){if(!d[x])continue;for(rint i=first[x];i;i=edge[i].nxt){if(belong[x]==belong[edge[i].v])continue;add2(belong[x],belong[edge[i].v]);deg[belong[edge[i].v]]++;}}*/for(rint i=1;i<=tot_q;i++)if(!deg[i])add2(tot_q+1,i);dfs(tot_q+1);cout<
View Code
