原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最大值
1.2 题目背景、允许、禁止与限制
背景：
有 nnn 门功课，每门课有对应的学分 sis_isi ，每一门课有一门或零门先修课（当 aaa 是 bbb 的先修课时，只有先学习 aaa 才能学习 bbb）
允许：
在 nnn 门功课中选择 mmm 门学习，问获得的最大学分
限制：
学习的课程必须满足先修课的限制
1.3 题目数据范围与猜测
1≤n,m≤300⟶O(nm2)1 \le n,m \le 300 \longrightarrow O(nm^2)1≤n,m≤300⟶O(nm2)
1.4 一句话概括题意
* 有一个森林
因为发现有些课没有先修课，那么是可以直接选择的，所以都需要与超级源点进行关系的建立
* 在森林中有先后选择的限制情况下最大化选 m+1m+1m+1 门课的总权值
为什么是 m+1m+1m+1？因为超级源点是一定要选的，否则其他所有课都无法选，但超级源点选上就会使选课数 mmm 变为 m+1m+1m+1
2 题目破题推导
2.1 第一步：分情况讨论
对于每个节点 uuu，在其子树内，选了 jjj 门课时：
* 只选 uuu 自己
* 选 uuu 自己 +++ 从所有子节点 vvv 对应的子树里选若干门课的学分
2.2 第二步：限制思想
当节点 uuu 的子树之内选了 jjj 门课时，每个子节点 vvv 可以分配多少门课呢？
可以是 i(i∈[0,j−1])i(i\in[0,j-1])i(i∈[0,j−1]) 门，因为必须要留一门给 uuu，当然所有子节点的课数总和应该是 j+1j+1j+1
3 模型匹配
关键词：树形结构，动态求取最大值 ⟶\longrightarrow⟶ 树形dp（背包问题）\huge{树形dp（背包问题）}树形dp（背包问题）
4 最终代码（禁止抄袭，仅用于参考）
