终于是道中文题了。。。。

当时考试的时候就考的这道题。。。。 果断GG。

思路：

因为有可能存在依赖环，所以呢 先要tarjan一遍 来缩点。

随后就进行一遍树形DP就好了。。

x表示当前的节点。j表示j的空间最多能放多少价值的软件。

状态转移方程：f[x][j]=max(f[x][j],f[x.son][k]+f[x][j-k])

题目说：软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作

这句话怎么翻译呢？ 直接把W[i]以下的价值设为负无穷不就好了嘛。。

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,xx,t=0,tot=0,cnt=0,top=0,maxx=0,low[105],dfn[105],s[105],p[105],D[105],f[505][505];

int first[105],next[105],v[105],W[105],WW[105],V[105],VV[105],vis[105],in[105];

void add(int x,int y){v[tot]=y,next[tot]=first[x];first[x]=tot++;}

void tarjan(int x){

    low[x]=dfn[x]=++cnt;vis[x]=1;s[++top]=x;

    for(int i=first[x];~i;i=next[i])

        if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]);

        else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]);

    if(low[x]==dfn[x]){t++;do xx=s[top--],vis[xx]=0,p[xx]=t,WW[t]+=W[xx],VV[t]+=V[xx];while(xx!=x);}

}

void dfs(int x){

    for(int i=first[x];~i;i=next[i]){

        dfs(v[i]);

        for(int j=m;j>=0;j--)

            for(int k=j;k>=0;k--)

                f[x][j]=max(f[x][j],f[v[i]][k]+f[x][j-k]);

    }

}

int main(){

    memset(first,-1,sizeof(first));

    memset(f,0xcf,sizeof(f));

    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]),add(D[i],i);

    for(int i=0;i<=n;i++)if(!dfn[i])tarjan(i);

    memset(first,-1,sizeof(first));

    for(int i=1;i<=n;i++)if(p[D[i]]!=p[i])add(p[D[i]],p[i]),in[p[i]]++;

    for(int i=1;i<=t;i++)if(!in[i]&&i!=p[0])add(p[0],i);

    for(int i=1;i<=t;i++)for(int j=WW[i];j<=m;j++)f[i][j]=VV[i];

    dfs(p[0]);

    printf("%d\n",f[p[0]][m]);

}