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个点
}