选课

题意：
你有n门课程，你可以选择m门课选修，有的课程有先修课，每一门课程都有学分，求你可获得的最大学分为多少？

思路：
树状dp
没先修课的与0节点连接，有先修课的与先修课连接，这样就是0节点为根的一棵树了。
dp[i][j]表示以i节点为根的子树且选择了i时共选择j门课程的最大学分，这样就满足了先修课的条件。
se[i]表示以i为根的子树的节点数。
根节点u，子节点v：
dp[u][r+l]=max(dp[u][r+l],dp[u][l]+dp[v][r]);
结果为dp[0][m];（0节点不是一门课，一开始m要+1，因为0节点一定会被选）

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=1000000007;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int k[305], dp[305][305], se[305], m;

vector<int> g[305];

void dfs(int v)
{
    se[v]=1;
    dp[v][1]=k[v];
    for(int i=0;i<g[v].size();i++)
    {
        dfs(g[v][i]);
        for(int l=min(se[v],m);l>=1;l--)
        {
            for(int r=0;r<=min(se[g[v][i]],m);r++)
            {
                if(l+r<=m)
                {
                    dp[v][r+l]=max(dp[v][r+l],dp[v][l]+dp[g[v][i]][r]);
                }
            }
        }
        se[v]+=se[g[v][i]];
    }
}

int main()
{
    int n;
    scanf("%d%d",&n,&m);
    m++;
    for(int i=1;i<=n;i++)
    {
        int u, t;
        scanf("%d %d",&u,&t);
        g[u].push_back(i);
        k[i]=t;
    }
    dfs(0);
    printf("%d\n",dp[0][m]);
    return 0;
}