世界真的很大
（还是纪念fate）
动态规划的题很常见了
其中背包问题也是屡见不鲜
而有时各个物品间有各种依赖关系，构成一颗树状的结构
有人将其称之为
树形依赖背包动态规划
还是先看一下题：
Description

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

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

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

input

第1@H_404_18@行：N,M  （0@H_404_18@<=N<=100@H_404_18@,0@H_404_18@<=M<=500@H_404_18@）
      第2@H_404_18@行：W1,W2,...@H_404_18@ Wi,...@H_404_18@,Wn （0@H_404_18@<=Wi<=M ）
      第3@H_404_18@行：V1,V2,Vi,Vn  （0@H_404_18@<=Vi<=1000@H_404_18@ ）
      第4@H_404_18@行：D1,D2,Di,Dn （0@H_404_18@<=Di<=N,Di≠i ）

output

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

其实能从题意里轻松读出来这是背包问题。
每一个物品向它依赖的物品连边，形成一种树形的结构，每个没有依赖的物品就是根节点。要想要每一个物品，它到它根节点的所有物品全都要取。
但这样就可能不止一棵树了
很容易想到虚拟一个点（如0）来作为所有树的根节点，这样就是一棵树了。再跑一遍树形依赖背包动态规划，就完事儿了
但这样有一个很坑的错误
每种联通的依赖关系，不见得是一棵树
比如1依赖2,2依赖1,没有问题.
所以不能直接虚拟一个点。
先用tarjan缩点，连边，这样才得到了很多的树，虚拟一个根节点，跑一遍树形dp就行了
完整代码：

#include<stdio.h>@H_404_18@
#include<cstring>@H_404_18@
#include<stack>@H_404_18@
using@H_404_18@ namespace@H_404_18@ std@H_404_18@;

stack@H_404_18@ <int@H_404_18@>@H_404_18@ state;

struct@H_404_18@ edge
{
    int@H_404_18@ last,u,v;
}ed[100010@H_404_18@],ad[100010@H_404_18@];

int@H_404_18@ num=0@H_404_18@,mum=0@H_404_18@,ans=0@H_404_18@,cnt=0@H_404_18@,n,m,idx=0@H_404_18@,INF=1e9@H_404_18@;
int@H_404_18@ head[1010@H_404_18@],dfn[1010@H_404_18@],low[1010@H_404_18@],ins[1010@H_404_18@],f[110@H_404_18@][510@H_404_18@];
int@H_404_18@ w[110@H_404_18@],v[110@H_404_18@],pt[110@H_404_18@],vis[110@H_404_18@],in[510@H_404_18@],ww[110@H_404_18@],vv[110@H_404_18@],hed[10010@H_404_18@];

void@H_404_18@ add(int@H_404_18@ u,int@H_404_18@ v)
{
    num++;
    ed[num].last=head[u];
    ed[num].v=v;
    ed[num].u=u;
    head[u]=num;
}

void@H_404_18@ ade(int@H_404_18@ u,int@H_404_18@ v)
{
    mum++;
    in[v]++;
    ad[mum].v=v;
    ad[mum].last=hed[u];
    hed[u]=mum;
}

void@H_404_18@ tarjan(int@H_404_18@ u)
{
    dfn[u]=low[u]=++idx;
    vis[u]=ins[u]=1@H_404_18@;
    state.push(u);
    for@H_404_18@(int@H_404_18@ i=head[u];i;i=ed[i].last)
    {
        int@H_404_18@ v=ed[i].v;
        if@H_404_18@(!vis[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else@H_404_18@ if@H_404_18@(ins[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if@H_404_18@(dfn[u]==low[u])
    {
        cnt++;int@H_404_18@ t=-1@H_404_18@;
        while@H_404_18@(t!=u)
        {
            t=state.top();
            pt[t]=cnt;
            ww[cnt]+=w[t];
            vv[cnt]+=v[t];
            ins[t]=0@H_404_18@;
            state.pop();
        }
    }
}

void@H_404_18@ dfs(int@H_404_18@ u)
{
    for@H_404_18@(int@H_404_18@ i=hed[u];i;i=ad[i].last)
    {
        int@H_404_18@ v=ad[i].v;
        dfs(v);
        for@H_404_18@(int@H_404_18@ k=m;k>=0@H_404_18@;k--)
            for@H_404_18@(int@H_404_18@ j=k;j>=0@H_404_18@;j--)
            f[u][k]=max(f[u][k],f[u][k-j]+f[v][j]);
    }
    for@H_404_18@(int@H_404_18@ j=m;j>=0@H_404_18@;j--)
    {
        if@H_404_18@(j>=ww[u]) f[u][j]=f[u][j-ww[u]]+vv[u];
        else@H_404_18@ f[u][j]=0@H_404_18@;
    }
}

void@H_404_18@ rebuild()
{
    memset@H_404_18@(head,0@H_404_18@,sizeof@H_404_18@(head));
    for@H_404_18@(int@H_404_18@ i=1@H_404_18@;i<=num;i++)
        if@H_404_18@(pt[ed[i].u]!=pt[ed[i].v])
        {
            ade(pt[ed[i].u],pt[ed[i].v]);
            in[pt[ed[i].v]]++;
        }
}

int@H_404_18@ main()
{
    scanf@H_404_18@("%d%d"@H_404_18@,&n,&m);
    for@H_404_18@(int@H_404_18@ i=1@H_404_18@;i<=n;i++)
        scanf@H_404_18@("%d"@H_404_18@,&w[i]);
    for@H_404_18@(int@H_404_18@ i=1@H_404_18@;i<=n;i++)
        scanf@H_404_18@("%d"@H_404_18@,&v[i]);
    for@H_404_18@(int@H_404_18@ i=1@H_404_18@;i<=n;i++)
    {
        int@H_404_18@ u;
        scanf@H_404_18@("%d"@H_404_18@,&u);
        add(u,i);
    }
    for@H_404_18@(int@H_404_18@ i=0@H_404_18@;i<=n;i++)
    if@H_404_18@(!vis[i]) tarjan(i);
    rebuild();
    int@H_404_18@ s;
    for@H_404_18@(int@H_404_18@ i=1@H_404_18@;i<=cnt;i++)
       if@H_404_18@(!in[i]) ade(cnt+1@H_404_18@,i);
    dfs(cnt+1@H_404_18@);
    printf@H_404_18@("%d"@H_404_18@,f[cnt+1@H_404_18@][m]);
    return@H_404_18@ 0@H_404_18@;
}

嗯，就是这样