记录编号	466230	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2017-10-28 17:36:25	内存使用	2.12 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int M=500+10;
int n,m,h,dex,num,cnt;
int pd[M],w[M],v[M],W[M],V[M],stack[M],dfn[M],low[M],belong[M];
int head[4*M],len[M],fa[M],f[M][M];
bool instack[M];
struct tree{int child[M],fa,ge;}tr[M];
struct DATE{int to,last;}date[4*M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y){
    date[++num]=(DATE){y,head[x]};
    head[x]=num;
}
void tarjan(int x){
    low[x]=dfn[x]=++dex;stack[h++]=x;instack[x]=1;
    for(int i=head[x];i;i=date[i].last){
        int to=date[i].to;
        if(!dfn[to]) tarjan(to),low[x]=min(low[x],low[to]);
        else if(instack[to]) low[x]=min(low[x],dfn[to]);
	}if(low[x]==dfn[x]){
        int temp;++cnt;
        do{
            temp=stack[--h];
            belong[temp]=cnt;
            W[cnt]+=w[temp];
            V[cnt]+=v[temp];
            len[cnt]+=1;
            instack[temp]=0;
        }while(temp!=x);
     }
}
void dp(int x){
    if(tr[x].ge==0){
        for(int i=W[x];i<=m;i++) f[x][i]=V[x];
        return ;
    }
    for(int i=1;i<=tr[x].ge;++i) dp(tr[x].child[i]);
    for(int i=1;i<=tr[x].ge;++i){
        int ch=tr[x].child[i];
        for(int i=m;i>=0;--i)
            for(int j=0;j<=i;++j)
               f[x][i]=max(f[x][i],f[x][i-j]+f[ch][j]);
    }
    for(int i=m;i>=0;--i){
        if(i>=W[x]) f[x][i]=f[x][i-W[x]]+V[x];
        else f[x][i]=0;
    }
}
int DK(){
	freopen("install.in","r",stdin);
    freopen("install.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;++i) w[i]=read();
    for(int i=1;i<=n;++i) v[i]=read();
    for(int i=1;i<=n;++i) fa[i]=read(),add(fa[i],i);
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    belong[0]=0;
    for(int i=1;i<=n;++i){
        if(belong[fa[i]]!=belong[i]){
          tr[belong[fa[i]]].ge+=1;
          tr[belong[fa[i]]].child[tr[belong[fa[i]]].ge]=belong[i];
          tr[belong[i]].fa=belong[fa[i]];
        }else pd[belong[i]]+=1;
    }for(int i=1;i<=cnt;++i)
        if(pd[i]==len[i]){
        	tr[0].ge+=1; tr[i].fa=0;
        	tr[0].child[tr[0].ge]=i;
        }
    dp(0);
    printf("%d\n",f[0][m]);
	return 0;
}
int dk=DK();
int main(){;}