lp2515 HAOI2010 软件安装

简单的tarjan缩点+树形背包DP。
考虑N<=100，M<=500，只需要设f[i][j]表示第i个点，已用j的容量。
然后直接DP即可。
特别地，由于如果某一个点的子树中的点被选中了，这个点也要被选中，所以我们在计算每个点的时候，一定要将这个点加进去。
然后仔细看看这道题，发现它不保证没有环！
这下完蛋了，咋做啊？
考虑到这个环要么都选，要么都不选，所以可以先用tarjan找环，把找环后的点拿来dfs。
然后我们考虑一个性质：如果存在环，那么这个环缩成的点一定是某一棵树的树根。
所以我们不妨计算每一个点的入度，然后将入度为0的点连向虚点0。这样只需要一次DP。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[505];
int h[505],g[505],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
int n,m,f[505][505],w[505],v[505],ww[505],val[505],d[505],in[505];
int vis[505],clr[505],dfn[505],lw[505],cnt=0,ccnt=0,st[505],tp=0;
inline void dfs0(int X){
	vis[X]=1,dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	for(int i=g[X];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);lw[X]=Min(lw[X],lw[e[i].v]);
		}else if(vis[e[i].v]){
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
	if(dfn[X]==lw[X]){
		++ccnt;
		while(st[tp+1]!=X){
			clr[st[tp]]=ccnt;
			val[ccnt]+=v[st[tp]],ww[ccnt]+=w[st[tp]];
			vis[st[tp]]=0;
			--tp;
		}
	}
}
inline void dfs1(int X){
	for(int i=ww[X];i<=m;++i){
		f[X][i]=val[X];
	}
	for(int i=h[X];i;i=e[i].nxt){
		dfs1(e[i].v);
		for(int j=m-ww[X];j>=0;--j){//j表示之前的子树的重量和。 
			for(int k=0;k<=j;++k){//k表示这棵子树的重量和。 
				f[X][j+ww[X]]=Max(f[X][j+ww[X]],f[e[i].v][k]+f[X][j-k+ww[X]]); 
			}
		}
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&v[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
		if(d[i]){
			add(g,d[i],i);
		}
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			dfs0(i);
		}
	}
	for(int i=1;i<=n;++i){
		if(clr[d[i]]!=clr[i]){
			add(h,clr[d[i]],clr[i]);
			++in[clr[i]];
		}
	}
	for(int i=1;i<=ccnt;++i){
		if(!in[i]){
			add(h,0,i);
		}
	}
	dfs1(0);
	printf("%d\n",f[0][m]);
}
int main(){
	init();
	return 0;
}