Description
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
Input
第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 ）
Output
一个整数，代表最大价值。
把环缩掉，跑一个树形背包即可
#include<bits/stdc++.h>
using namespace std;
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 600
int edges,n,m;
int w[maxn],cost[maxn],hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn];
void addedge(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
map<int,int>M[maxn];
int num,scc;
vector<int>G[maxn];
stack<int>S;
int dfn[maxn],low[maxn],W[maxn],V[maxn],idx[maxn],vis[maxn];
void tarjan(int u)
{
low[u]=dfn[u]=++scc,vis[u]=1;
S.push(u);
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(!vis[v]) tarjan(v), low[u]=min(low[u],low[v]);
else if(vis[v]==1) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++num;
for(;;)
{
int x=S.top(); S.pop();
vis[x]=-1;
W[num]+=cost[x], V[num]+=val[x], idx[x]=num;
if(x==u) break;
}
}
}
int f[maxn][1200],tmp[maxn][1200],du[maxn];
void solve(int x)
{
for(int i=W[x];i<=m;++i) f[x][i]=V[x];
for(int i=0;i<G[x].size();++i)
{
int v=G[x][i];
solve(v);
for(int j=m-W[x];j>=0;--j)
{
for(int q=0;q<=j;++q)
{
f[x][W[x]+j]=max(f[x][W[x]+j], f[x][W[x]+j-q] + f[v][q]);
}
}
}
}
int main()
{
int i,j;
// setIO("input");
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) scanf("%d",&cost[i]);
for(i=1;i<=n;++i) scanf("%d",&val[i]);
for(i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
addedge(x,i);
}
for(i=1;i<=n;++i) if(!vis[i]) tarjan(i);
for(i=1;i<=n;++i)
{
int cur=idx[i];
for(j=hd[i];j;j=nex[j])
{
int v=idx[to[j]];
if(cur!=v&&!M[cur][v])
{
M[cur][v]=1;
G[cur].push_back(v);
++du[v];
}
}
}
for(i=1;i<=num;++i) if(du[i]==0) G[0].push_back(i);
solve(0);
printf("%d\n",f[0][m]);
return 0;
}