Luogu 2014 選課

題目連結：​​傳送門​​

題目描述

在大學裡每個學生，為了達到一定的學分，必須從很多課程裡選擇一些課程來學習，在課程裡有些課程必須在某些課程之前學習，如高等數學總是在其它課程之前學習。現在有N門功課，每門課有個學分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即隻有學完了課程a，才能學習課程b）。一個學生要從這些課程裡選擇M門課程學習，問他能獲得的最大學分是多少？

輸入格式：

第一行有兩個整數N,M用空格隔開。(1<=N<=300,1<=M<=300)

接下來的N行,第I+1行包含兩個整數ki和si, ki表示第I門課的直接先修課，si表示第I門課的學分。若ki=0表示沒有直接先修課（1<=ki<=N, 1<=si<=20）。

輸出格式：

隻有一行，選M門課程的最大得分。

輸入樣例

7 4

2 2

0 1

0 4

2 1

7 1

7 6

2 2

輸出樣例

13

咳

樹形dp的入門題

樹形背包的入門題

對于每一個搜到的節點

我們可以選它

這樣就還可以選它的孩子

是以有

如果我們不選這個節點

它的孩子就不能選了

是以

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define
#define
#define

using namespace std;
struct node {
  int next, to;
}edge[A];
int n, m, x, s, w[A], f[B][B];
int head[A], num_edge;
void add_edge(int from, int to) {
  edge[++num_edge].next = head[from];
  edge[num_edge].to = to;
  head[from] = num_edge;
}
void dfs(int fr, int deep) { //deep為目前點的深度
  for (int i = head[fr]; i; i = edge[i].next) {
    int ca = edge[i].to;
    for (int j = deep + 1; j <= m + 1; j++) f[ca][j] = f[fr][j - 1] + w[ca];
    dfs(ca, deep + 1); //先找出下面的狀态
    for (int j = deep + 1; j <= m + 1; j++) f[fr][j] = max(f[fr][j], f[ca][j]);
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> x >> w[i];
    add_edge(x, i);
  }
  dfs(0, 1);
  cout << f[0][m + 1]; //由于選了0号點是以要選m+1個點
}