CTSC 选课

题面（有删减）

题目描述
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
输入输出格式
输入格式：
第一行有两个整数N,M用空格隔开。(1<=N<=200,1<=M<=150)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
输出格式：
只有一行，选M门课程的最大得分。
输入输出样例
输入样例#1：
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例#1：
13
数据范围及提示 Data Size & Hint
各个测试点1s

---

CTSC的题目，看到时吓尿了。。。
恐怖。
害怕。
然而这是一道裸的树形DP（刚接触不久）

思路

建图都会吧，每堂课和学它必修的课连一条边。为了方便，每个入度为0的课（即可以直接选的课）与一个虚拟的n+1节点连一条边，然后在树上跑01背包即可。
以前的题目就是水，这让我想起了IOI数字三角形

常数巨大的丑陋代码

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
using namespace std;

# define IL inline
# define RG register
# define UN unsigned
# define ll long long
# define rep(i, a, b) for(RG int i = a; i <= b; i++)
# define per(i, a, b) for(RG int i = b; i >= a; i--)
# define uev(e, u) for(RG int e = ft[u]; e != -1; e = edge[e].nt)
# define mem(a, b) memset(a, b, sizeof(a))
# define max(a, b) ((a) > (b)) ? (a) : (b)
# define min(a, b) ((a) < (b)) ? (a) : (b)

IL int Get(){
    RG char c = '!'; RG int num = 0, z = 1;
    while(c != '-' && (c > '9' || c < '0')) c = getchar();
    if(c == '-') z = -1, c = getchar();
    while(c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar();
    return num * z;
}

const int MAXN = 302, INF = 2147483647;
struct Edge{
    int to, nt;
} edge[MAXN << 1];
int n, m, ft[MAXN], cnt, in[MAXN], w[MAXN], f[MAXN][MAXN];

IL void DP(RG int u){
    rep(i, 1, m) f[u][i] = w[u];
    uev(e, u){
        RG int v = edge[e].to;
        DP(v);
        per(i, 2, m)
            per(j, 1, i - 1)
                f[u][i] = max(f[u][i], f[u][j] + f[v][i - j]);
    }
}

int main(){
    mem(ft, -1);
    n = Get(); m = Get() + 1;
    rep(i, 1, n){
        RG int v = Get(); w[i] = Get();
        if(!v) continue;
        edge[cnt] = (Edge){i, ft[v]}; ft[v] = cnt++;
        in[i]++;
    }
    rep(i, 1, n) if(!in[i]) edge[cnt] = (Edge){i, ft[n + 1]}, ft[n + 1] = cnt++;
    DP(n + 1);
    printf("%lld
", f[n + 1][m]);
    return 0;
}