【题解】[HAOI2010] 软件安装 Tarjan 缩点、树形 DP LuoguP2515

蒟蒻的 Q 啦：1208247864 owo dalao 们来加啦

这个题很容易想到树上做背包
复杂度 O(nm^2)
完全可过

具体做法就是说我们先建边，然后去 dfs
令当前节点为 x 即将要去的节点为 go
由于是有向边，所以没必要判断 go == fa[x]
然后处理 go
返回后，在 x 这里做一次背包即可

然而还是有坑点的
图中的点不一定联通
这令人十分尴尬
而且可能会出现环
既然是环，那我们去观察环的性质
环上所有点要么都选要么都不选
所以我们可以想到缩点，当然首选 Tarjan ^ _ ^

缩完点之后，就成了一群 DAG
也可以看为树
那么我们可以把所有的根，即 DAG 中入度为 0 的点
连到 0 上，然后成为了一棵树
然后就是像上面做一次在树上的背包就好了

#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 510
using namespace std;

IL void of(R II &a) {
    R char c=getchar (); R II w=1, p=0;
    while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar (); }
    while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar (); }
    a=w*p;
}

/* -------------------- Peipei -------------------- */

II n,V,root,_tot,all,_top,bit;
II head[I], f[I][I], w[I], v[I], in[I], belong[I], kl[I], VV[I];
II DFN[I], LOW[I], Stack[I], cant[I], vis[I], W[I], had[I][I]; 

struct owo { II to,up; } aa[I], edge[I];
IL void add(R II x,R II y) {
    aa[++_tot]=(owo) {y,head[x]};
    head[x]=_tot;
}

IL void Tarjan(R II x) {
    DFN[x]=LOW[x]=++all;
    Stack[++_top]=x;
    vis[x]=1;
    for(R II i=head[x],go;i;i=aa[i].up)
    {
        go=aa[i].to;
        if(!DFN[go]) {
            Tarjan(go);
            LOW[x]=min(LOW[x],LOW[go]);
        } else if(vis[go]) LOW[x]=min(LOW[x],DFN[go]);
    }

    if(DFN[x]==LOW[x]) {
        bit++;
        do {
            R II o=Stack[_top--];
            vis[o]=0; 
            belong[o]=bit;
            W[bit]+=w[o];
            VV[bit]+=v[o];
        } while (Stack[_top+1]!=x) ;
    }
}

IL void dfs(R II x) {
    for(R II i=VV[x];i<=V;i++) f[x][i]=W[x];
    for(R II i=head[x],go;i;i=aa[i].up)
    {
        go=aa[i].to;
        dfs(go);
        for(R II j=V-VV[x];j>=0;j--)
        for(R II k=j;k>=0;k--) 
            f[x][j+VV[x]]=max(f[x][j+VV[x]],f[x][j+VV[x]-k]+f[go][k]);
    }
}

int main()
{
    of(n); of(V);
    for(R II i=1;i<=n;i++) of(v[i]);
    for(R II i=1;i<=n;i++) of(w[i]);
    for(R II i=1,x;i<=n;i++) 
    {
        of(x); 
        if(!x) continue ; 
        add(x,i); in[i]++;
    }


    for(R II i=1;i<=n;i++) if(!DFN[i]) Tarjan(i);
    for(R II i=1;i<=_tot;i++) edge[i]=aa[i];
    for(R II i=1;i<=n;i++) kl[i]=head[i], head[i]=0;
    for(R II i=1;i<=n;i++) had[i][i]=1, in[i]=0;
    _tot=0;

    for(R II x=1;x<=n;x++)
    {
        for(R II i=kl[x],go;i;i=edge[i].up)
        {
            go=edge[i].to;
            if(!had[belong[x]][belong[go]]) {
                add(belong[x],belong[go]);
                had[belong[x]][belong[go]]=1;
                in[belong[go]]++;
            }
        }
    }

    for(R II i=1;i<=bit;i++) if(!in[i]) add(0,i);
    dfs(0);
    printf("%d\n",f[0][V]);
}