记录编号	331003	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]软件安装	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.202 s
提交时间	2016-10-27 07:08:56	内存使用	0.55 MiB

#include <queue>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ll long long 
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-48,ch=getchar();
	return x*f;
}
const int maxn=110;
struct edge{int to,next;}e[maxn];
int tot,head[maxn];
void add(int u,int v){
	e[++tot].to=v;
	e[tot].next=head[u];
	head[u]=tot;
}
int dfn[maxn],low[maxn],q[maxn],top;
int fa[maxn],c[maxn],w[maxn],C[maxn],W[maxn];
int dfs_cnt,scc_cnt,sccno[maxn],n,m;
int num[maxn],f[maxn][maxn*5],lc[maxn],rc[maxn];
void dfs(int u){
	dfn[u]=low[u]=++dfs_cnt;
	q[++top]=u;
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(!dfn[to]){dfs(to);low[u]=min(low[u],low[to]);}
		else if(!sccno[to]) low[u]=min(low[u],dfn[to]);
	}
	if(dfn[u]==low[u]){
		++scc_cnt;
		for(;;){
			int x=q[top--];
			sccno[x]=scc_cnt;
			C[scc_cnt]+=c[x];
			W[scc_cnt]+=w[x];
			num[scc_cnt]++;
			if(x==u)break;
		}
	}
}
int dp(int rt,int left){
	if(!left||rt<=0)return 0;
	if(f[rt][left]) return f[rt][left];
	f[rt][left]=dp(rc[rt],left);
	for(int i=W[rt];i<=left;i++)
		f[rt][left]=max(f[rt][left],dp(lc[rt],i-W[rt])+C[rt]+dp(rc[rt],left-i));
	return f[rt][left];
}

int main(){
	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++)c[i]=read();
	for(int i=1;i<=n;i++)fa[i]=read();

	for(int i=1;i<=n;i++) if(fa[i])add(i,fa[i]);
	for(int i=1;i<=n;i++) if(!dfn[i])dfs(i);
	sccno[0]=scc_cnt+1;
	for(int i=1;i<=n;i++)
		if(sccno[i]!=sccno[fa[i]])
			if(!lc[sccno[fa[i]]])lc[sccno[fa[i]]]=sccno[i];
			else{
				int x=lc[sccno[fa[i]]];
				lc[sccno[fa[i]]]=sccno[i];
				rc[sccno[i]]=x;
			}
	for(int i=1;i<=scc_cnt;i++)
		if(num[i]>1)
			if(!lc[scc_cnt+1])lc[scc_cnt+1]=i;
			else{
				int x=lc[scc_cnt+1];
				lc[scc_cnt+1]=i;
				rc[i]=x;
			}
	printf("%d\n",dp(scc_cnt+1,m));
	fclose(stdin);fclose(stdout);
	return 0;
}