直接树形dp就好了恩
令$f[i][j][t]$表示以$i$为根的子树，选出来的点存在$j$对父子关系，$t$表示$i$这个点选或者没选，的最大产奶值
分类讨论自己和儿子分别有没有选，然后转移一下就好了。。。恩，详情看代码好了
1 /************************************************************** 2 Problem: 1722 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:28 ms 7 Memory:2808 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 const int N = 505; 15 const int inf = 1e9; 16 17 struct edge { 18 int next, to; 19 edge(int _n = 0, int _t = 0): next(_n), to(_t) {} 20 } e[N]; 21 22 struct tree_node { 23 int v, fa; 24 } tr[N]; 25 26 int n, tar, ans; 27 int first[N], tot; 28 int f[N][N][2]; 29 30 inline void add_edge(int x, int y) { 31 e[++tot] = edge(first[x], y); 32 first[x] = tot; 33 } 34 35 #define y e[x].to 36 void dfs(int p) { 37 int t1, t2, tmp, i, j, x; 38 static int t[N]; 39 f[p][0][0] = 0, f[p][0][1] = tr[p].v; 40 for (i = 1; i < n; ++i) 41 f[p][i][0] = f[p][i][1] = -inf; 42 if (first[p] == 0) return; 43 for (x = first[p]; x; x = e[x].next) { 44 dfs(y); 45 for (t1 = 0; t1 < 2; ++t1) { 46 for (j = 0; j < n; ++j) t[j] = f[p][j][t1]; 47 for (t2 = 0; t2 < 2; ++t2) { 48 tmp = t1 && t2 && p; 49 for (i = 0; i < n; ++i) if (f[y][i][t2] != -inf) 50 for(j = n - 1; i + tmp <= j; --j) 51 if (f[p][j - i - tmp][t1] != -inf) 52 t[j] = max(t[j], f[p][j - i - tmp][t1] + f[y][i][t2]); 53 } 54 for (j = 0; j < n; ++j) f[p][j][t1] = max(f[p][j][t1], t[j]); 55 } 56 } 57 58 } 59 #undef y 60 61 int main() { 62 int i; 63 scanf("%d%d", &n, &tar); 64 for (i = 1; i <= n; ++i) { 65 scanf("%d%d", &tr[i].v, &tr[i].fa); 66 add_edge(tr[i].fa, i); 67 } 68 dfs(0); 69 for (ans = n - 1; ~ans && f[0][ans][0] < tar; --ans); 70 printf("%d ", ans); 71 return 0; 72 }