思路

一开始我还以为是拓扑排序，后面写代码的时候仔细思考了这道题，应该是树形dp。

主要的思路就是做一个编号为0的虚拟节点（这个点权重（学分）为0），然后建一棵树。构造dp方程\(F[u][size] = F[son][subsize] + F[u][size – subsize]\)。其中这里需要注意的是，这个本质上是一个树形的01背包，所以在生成dp表的时候需要反着推。（坑了我一个小时，哎我还是太菜了）输出的时候因为有点0的存在所以背包容量会比之前的大一个单位。

还需要注意的是，在我的代码中，我用了一个dfss来计算每个子背包的容量，不知道有没有必要，希望大佬能指出是否有这个必要。

代码

// P2014.cpp
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 2100;
struct edge
{
    int to, next;
} edges[maxn << 1];
int deg[maxn];
int indeg[maxn];
int head[maxn];
int weight[maxn];
int current = 0;

int n, m;

void addpath(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int F[maxn][maxn];
int sizes[maxn];

void dfss(int u)
{
    sizes[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfss(edges[i].to);
        sizes[u] += sizes[edges[i].to];
    }
}

void dfs(int u)
{
    for (int i = 1; i <= m; i++)
        F[u][i] = weight[u];
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfs(edges[i].to);
        int jto = edges[i].to;
        for (int len = m + 1; len >= 2; len--)
            for (int lens = 0; lens < len; lens++)
                F[u][len] = max(F[u][len], F[u][len - lens] + F[jto][lens]);
    }
}

int main()
{
    fill(head, head + maxn, -1);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int k, s;
        cin >> k >> s;
        weight[i] = s;
        addpath(k, i), indeg[i]++, deg[k]++;
    }
    dfss(0);
    dfs(0);
    cout << F[0][m + 1];
    return 0;
}