刚接触树状DP,好难啊QAQ

[CTSC1997] 选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有

输入格式

第一行有两个整数

接下来的

输出格式

只有一行，选

输入输出样例

输入 #1

输出 #1

//本题略有变形,多加思考
#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int f[N][N],w[N]={1},v[N],h[N],e[N],ne[N],idx,res,n,m,root;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int son=e[i];
        dfs(son);
        for(int j=m;j>=0;j--)//这里为什么要从m开始呢?
    //如标题所示,这个是树状dp的问题,但是按照题意来的话,画完图之后很明显是森林
    //这个时候我们就需要多建立一个0节点来使他们形成树
            for(int k=0;k<=j;k++) f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
    }
    for(int i=m+1;i>=1;i--) f[u][i]=f[u][i-1]+v[u];
    f[u][0]=0;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<=m+1;i++) f[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p>>v[i];
        //f[i][1]=v[i];
        add(p,i);
    }
    dfs(0);
    cout<<f[0][m+1];//这里的m+1就是因为多建了个节点,0节点是必须选的,但是呢0节点的价值是0;
    return 0;
}