【树形DP】P2014 选课

 1 #include<iostream>
 2 #include<string>
 3 #include<queue>
 4 #include<stack>
 5 #include<vector>
 6 #include<map>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<algorithm>
10 #include<set>
11 #include<list>
12 #include<iomanip>
13 #include<cstring>
14 #include<cmath>
15 #include<limits>
16 using namespace std;
17 
18 #define au auto
19 #define debug(i) cout<<"<debug> "<<i<<"<\debug>"<<endl
20 #define mfor(i,a,b) for(register int i=(a);i<=(b);i++)
21 #define mrep(i,a,b) for(register int i=(a);i>=(b);i--)
22 #define LLL __int128
23 #define Re register
24 #define il inline
25 #define mem(a,b) memset(a,(b),sizeof(a))
26 typedef pair<int, int> intpair;
27 typedef long long int LL;
28 const int INF = 0x3f3f3f3f;
29 const long long int INFLL = 0x3f3f3f3f3f3f3f3f;
30 
31 int cnt;
32 int n, m;
33 const int maxn = 1010;
34 int f[maxn][maxn];
35 
36 struct Edge
37 {
38     int u, nxt;
39 }e[maxn];
40 
41 int head[maxn];
42 
43 void add(int a, int b)
44 {
45     e[++cnt].u = b;
46     e[cnt].nxt = head[a];
47     head[a] = cnt;
48 }
49 
50 void dp(int x)
51 {
52     for (Re int i = head[x]; i != -1; i = e[i].nxt)
53     {
54         int u = e[i].u;
55         dp(u);
56         mrep(j, m + 1, 1)
57         {
58             mfor(k, 0, j - 1)
59             {
60                 f[x][j] = max(f[x][j], f[u][k] + f[x][j - k]);
61             }
62         }
63     }
64 }
65 
66 int main()
67 {
68     mem(head, -1);
69     cin >> n >> m;
70     mfor(i, 1, n)
71     {
72         Re int a, b;
73         cin >> a >> b;
74         f[i][1] = b;
75         add(a, i);
76     }
77     dp(0);
78     cout << f[0][m + 1];
79 }