1378 选课
原题：https://codevs.cn/problem/1378/
题目描述 Description
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。
在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。 例如:
【详见图片】
表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。 你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
输入描述 Input Description
输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。
以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。
输出描述 Output Description
输出文件只有一个数,实际所选课程的学分总数。
样例输入 Sample Input
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
样例输出 Sample Output
13
个人解法：
这的确是树DP的经典了，树DP的基本知识都挂上了（当然，至于最大直径一类拓展，这题还是没用到……）。
我们用f[i,j]表示到第i个节点分配j的代价所能达到的最大价值。
首先包括一个建树过程，每一个节点就代表这一个课程，节点的父亲就是该课程的先修课程。因为对于某一门课程只有一门先修课，所以不会有一个节点两个父亲的局面，所以就可以放放心心地建树。
接着我们就要处理一个非二叉树转换为二叉树的问题。
我们把所有节点的兄弟变为它的右儿子，它的儿子变为它的左儿子，这样就把一棵多叉树变成了一棵二叉树。
当然DP方程式也有变化。
因为此时选择当前节点的左儿子就必须选择当前的节点，而选择当前节点的右儿子不必选择当前节点。所以DP方程为：
f[i,j]=max(f[r,j],f[l,k]+f[r,j-k-cost[i]]+w[i])，其中0<=k<=j-cost[i]。
当然这里还有一个注意点：
我们发现数据时可以构成一个森林的，那么我们就需要一个虚拟节点来连接所有的树的根节点。
我相信某些懒人，像我一样直接用0来作为虚拟节点。
这样我们在求的最终答案的时候，如果用f[0,i]来求就会得出错误答案。
为什么呢？
看到我们的DP方程式。当k>0的时候，我们发现之前的f[0,l](0<=l<=k)已经有值了（也就是不等于0）。那么这个时候我们求出的f[0,k]事实上就累加了之前某一个f[0,l]的值。
那为什么在其他节点不会有这样的问题呢？因为在其他节点求状态最优的时候，f[0,l](0<=l<=m(m为最大代价))一直是0，所以不会影响答案。
所以，我们在求得答案的时候，就用f[tree[0].l,m]来求就好了。
这里困扰了我两天啊……再一次感谢学长。
代码如下：
uses math;//懒人调用的数学函数库
type
treenode=record
l,r,data:longint;
end;
var
tree:array[0..300] of treenode;
f:array[0..300,0..300] of longint;
cost:array[0..300] of longint;
n,m,a,b,c,i,ans:longint;
procedure ins(f,s:longint);//就是以f为父亲，以s为左儿子建立关系。
begin
if tree[f].l=0 then tree[f].l:=s//如果左儿子是空的，那么直接建立就好
else
begin
f:=tree[f].l;//如果f的左儿子不是空的，那么s就应该是tree[f].l的兄弟节点，也就是tree[f].l的右儿子。
while tree[f].r<>0 do
f:=tree[f].r;
tree[f].r:=s;
end;
end;
procedure dfs(i:longint);
var
j,k:longint;
begin
if tree[i].l<>0 then dfs(tree[i].l);
if tree[i].r<>0 then dfs(tree[i].r);//回溯DP
for j:=0 to m do
begin
f[i,j]:=f[tree[i].r,j];
for k:=0 to j-cost[i] do
f[i,j]:=max(f[i,j],f[tree[i].l,k]+f[tree[i].r,j-k-cost[i]]+tree[i].data);//动态转移方程
end;
end;
begin
read(n,m);
for i:=1 to n do
begin
read(a,b);
ins(a,i);//建树
tree[i].data:=b;
end;
for i:=1 to n do
cost[i]:=1;
dfs(0);
writeln(f[tree[0].l,m]);//很重要！！！
end.
一个困扰了我两天的题终于过了。当然在学长的指点中又发现了查找错误的神奇方法。总之自明自己实力不足，才能谦虚地不断进步。
当然，如果各位还有什么质疑欢迎提出。如果还有什么问题也乐意帮助。
4月份就省选了。这样的水平该是怎样的自嘲，我说不清楚……
不过，DP路上，还是希望与你们共同进步。