LibreOJ 10154 選課

題目連結：LibreOJ 10154 選課

題目大意：

題解：

樹上的背包問題。

不妨給所有沒有先修課程的課增加先修課程\(0\)，設\(dp[i][j]\)表示以\(i\)作為根的子樹修讀\(j\)門課獲得的最大學分。

狀态轉移方程：

\[dp[u][i] = max\{dp[u][i], dp[u][i - j] + dp[v][j]\}

\]

由于想要這棵子樹上的學分，\(u\)為必修課程，是以還需要更新一遍\(u\)的學分。

\[dp[u][i] = dp[u][i - 1] + score[u]

答案為\(dp[0][m]\)。