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

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 128;
const int maxm = 512;
struct Edge{
	int to,next;
}G[maxn<<1],g[maxn<<1];
int head[maxn],cnt,h[maxn],ct;
void add(int u,int v){
	G[++cnt].to = v;
	G[cnt].next = head[u];
	head[u] = cnt;
}int deg[maxn];
void gadd(int u,int v){
	++deg[v];
	g[++ct].to = v;
	g[ct].next = h[u];
	h[u] = ct;
}
int scccnt,sccnode[maxn],low[maxn],dfn[maxn],Rt;
int dfs_clock,sta[maxn],top,sccw[maxn],sccsp[maxn];
int w[maxn],sp[maxn],n,m;
#define v G[i].to
void dfs(int u){
	dfn[u] = low[u] = ++ dfs_clock;
	sta[++top] = u;
	for(int i = head[u];i;i=G[i].next){
		if(!dfn[v]){
			dfs(v);
			low[u] = cat_min(low[u],low[v]);
		}else if(!sccnode[v]) low[u] = cat_min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u]){
		++scccnt;
		while(1){
			int x = sta[top--];
			sccnode[x] = scccnt;
			sccw[scccnt] += w[x];
			sccsp[scccnt] += sp[x];
			if(x == u) break;
		}
	}
}
#undef v
inline void tarjan(){
	for(int i=1;i<=n;++i){
		if(!dfn[i]) dfs(i);
	}
}
int f[maxn][maxm];
#define v g[i].to
void dp(int u){
	for(int i = h[u];i;i=g[i].next){
		dp(v);
		for(int j = m - sccsp[u];j>=0;--j){
			for(int k=0;k<=j;++k){
				f[u][j] = cat_max(f[u][j],f[u][k] + f[v][j-k]);
			}
		}
	}
	for(int i=m;i>=0;--i){
		if(i >= sccsp[u]) f[u][i] = f[u][i - sccsp[u]] + sccw[u];
		else f[u][i] = 0;
	}
}
#undef v
int main(){
	freopen("install.in","r",stdin);
	freopen("install.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;++i) read(sp[i]);
	for(int i=1;i<=n;++i) read(w[i]);
	for(int i=1,x;i<=n;++i){
		read(x);
		if(x) add(x,i);
	}
	tarjan();
	for(int u=1;u<=n;++u){
		for(int i = head[u];i;i=G[i].next){
			if(sccnode[u] != sccnode[G[i].to]){
				gadd(sccnode[u],sccnode[G[i].to]);
			}
		}
	}
	int Rt = scccnt + 1;
	for(int i=1;i<=scccnt;++i){
		if(!deg[i]) gadd(Rt,i);
	}
	dp(Rt);
	printf("%d",f[Rt][m]);
	getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}