Description

现在我们的手头有N个软件，对于一个软件i，它要占用W_i的磁盘空间，它的价值为V_i。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即V_i的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件D_i。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则D_i=0，这时只要这个软件安装了，它就能正常工作。

 

Input

第1行：N, M  （0<=N<=100, 0<=M<=500）

      第2行：W₁, W₂, ... W_i, ..., W_n （0<=W_i<=M ）

      第3行：V₁, V₂, ..., V_i, ..., V_n  （0<=Vi<=1000 ）

      第4行：D₁, D₂, ..., D_i, ..., D_n（0<=D_i<=N, D_i≠i ）

 

Output

一个整数，代表最大价值。

 

Sample Input

3 10

5 5 6

2 3 4

0 1 1

Sample Output

5

HINT

 

Source

 

题解：

先tarjan缩下点，使其变成一棵树，然后我们就可以进行树上背包了

设f[u][i]表示选到u，用了空间i，得到的最大收益是多少

O（nm

²）的转移显然，但其实可以优化到O（nm）

设u的一个儿子是v，则我们可以把f[u]作为初始状态直接付给f[v]，然后就可以减少一个m的转移复杂度

注意把f[u]作为初始状态直接付给f[v]时，f[v]的第二维有下限（就是v及其所有祖先所占的空间和）

code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 char ch; 8 bool ok; 9 void read(int &x){10     ok=0;11     for (ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;12     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());13     if (ok) x=-x;14 }15 const int maxn=105;16 const int maxm=505;17 const int inf=1010580541;18 int n,m,a[maxn],b[maxn],x,ans;19 int f[maxn][maxm],g[maxm];20 int idx,dfn[maxn],low[maxn],stack[maxn],top,cnt,bel[maxn],siz[maxn],val[maxn],deg[maxn];21 bool in[maxn],bo[maxn];22 struct Graph{23     int tot,now[maxn],son[maxn],pre[maxn];24     void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}25     void dfs(int u){26         dfn[u]=low[u]=++idx,stack[++top]=u,in[u]=1;27         for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])28             if (!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);29             else if (in[v]) low[u]=min(low[u],dfn[v]);30         if (dfn[u]==low[u]){31             int v; ++cnt;32             do{v=stack[top--],bel[v]=cnt,siz[cnt]+=a[v],val[cnt]+=b[v],in[v]=0;}while (u!=v);33         }34     }35     /*void dp(int u){36         bo[u]=1;37         memset(f[u],195,sizeof(f[u]));38         f[u][siz[u]]=val[u];39         for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) if (!bo[v]){40             dp(v);41             memcpy(g,f[u],sizeof(g));42             for (int i=0;i<=m;i++) for (int j=m;j>=i;j--) g[j]=max(g[j],f[v][i]+f[u][j-i]);43             memcpy(f[u],g,sizeof(g));44         }45         f[u][0]=max(f[u][0],0);46     }*/47     /*void dp(int u,int m){48         //cout<
           <<' '<
            
             <