★★☆ 输入文件：install.in 输出文件：install.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一 些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大(即Vi的和最大)。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的 是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一 次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
【输入格式】
第1行：N，M (0<=N<=100．0<=M<=500)
第2行：W1，W2，…，Wi，…，Wn(0<=Wi<=M)
第3行：V1，V2，…，Vi，…，Vn(0<=Vi<=1000)
第4行：D1，D2，…，Di，…，Dn(0<=Di<=N，Di≠i)
【输出格式】
一个整数，代表最大价值。
【输入样例】
3 10
5 5 6
2 3 4
0 1 1
【输出样例】
5
题解：
根据依赖关系可以画出来一张图，有三种可能的情况：1.依赖关系构成一棵树 2.依赖关系构成一个环 3.依赖关系构成一个环下面吊着一棵树。因为有2,3这些情况，所以要先有tarjan预处理一下，缩环为点，重新建图。
对于建好的图，跑一边树形背包即可，思想类似于01背包，f[x][tot]表示以x为根，容量为tot的最大收益。把x的各个子树看成物品，再枚举每个子树所分给的容量，tot从大到小转移。
还有一点，f[x][tot]保证x要算进去，最后处理一下即可保证。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=,maxm=;
int N,M,W[maxn],V[maxn],fa[maxn];
int val[maxn],cost[maxn],f[maxn][maxm]; vector<int> to[maxn],son[maxn];
int stac[maxn],top=,dfn[maxn],low[maxn],inkin[maxn],tot,Index;
bool instac[maxn];
vector<int> kin[maxn];
inline void tarjan(int x){
dfn[x]=low[x]=Index++;
stac[++top]=x;
instac[x]=true;
for(int i=;i<to[x].size();i++){
int y=to[x][i];
if(dfn[y]==-){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(instac[y]!=){
low[x]=min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
tot++;
int y;
do{
y=stac[top--];
instac[y]=false;
kin[tot].push_back(y);
inkin[y]=tot;
}while(y!=x);
}
}
inline void calc(int x){
if(son[x].size()==){
for(int i=cost[x];i<=M;i++) f[x][i]=val[x];
return ;
}
for(int i=;i<son[x].size();i++) calc(son[x][i]); for(int i=;i<son[x].size();i++){
int y=son[x][i];
for(int tot=M;tot>=;tot--){
for(int j=;j<=tot;j++){
f[x][tot]=max(f[x][tot],f[x][tot-j]+f[y][j]);
}
}
}
for(int i=M;i>=;i--){
if(i>=cost[x]) f[x][i]=f[x][i-cost[x]]+val[x];
else f[x][i]=;
}
}
int main(){
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++) scanf("%d",&W[i]);
for(int i=;i<=N;i++) scanf("%d",&V[i]);
for(int i=;i<=N;i++){
scanf("%d",&fa[i]);
to[fa[i]].push_back(i);
}
memset(dfn,-,sizeof(dfn));
for(int i=;i<=N;i++){
if(dfn[i]==-) tarjan(i);
}
for(int i=;i<=tot;i++){
int y=kin[i][];
if(kin[i].size()>=){//形成一个环 ,取其中任意一点，缩环为点
val[y]=V[y]; cost[y]=W[y];
son[].push_back(y);
for(int j=;j<kin[i].size();j++){
val[y]+=V[kin[i][j]];
cost[y]+=W[kin[i][j]];
}
}
else{//是一棵树上的某一点，直接复制
if(fa[y]==)
son[].push_back(y);
else{
int xx=inkin[fa[y]];
int yy=kin[xx][];
son[yy].push_back(y);
}
val[y]=V[y]; cost[y]=W[y];
}
}
val[]=; cost[]=; calc();
printf("%d",f[][M]);
return ;
}