BZOJ1722 [Usaco2006 Mar] Milk Team Select 产奶比赛

直接树形dp就好了恩

令$f[i][j][t]$表示以$i$为根的子树，选出来的点存在$j$对父子关系，$t$表示$i$这个点选或者没选，的最大产奶值

分类讨论自己和儿子分别有没有选，然后转移一下就好了。。。恩，详情看代码好了

 /**************************************************************

     Problem: 1722

     User: rausen

     Language: C++

     Result: Accepted

     Time:28 ms

     Memory:2808 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int N = ;

 const int inf = 1e9;

 struct edge {

     int next, to;

     edge(int _n = , int _t = ): next(_n), to(_t) {}

 } e[N];

 struct tree_node {

     int v, fa;

 } tr[N];

 int n, tar, ans;

 int first[N], tot;

 int f[N][N][];

 inline void add_edge(int x, int y) {

     e[++tot] = edge(first[x], y);

     first[x] = tot;

 }

 #define y e[x].to

 void dfs(int p) {

     int t1, t2, tmp, i, j, x;

     static int t[N];

     f[p][][] = , f[p][][] = tr[p].v;

     for (i = ; i < n; ++i)

         f[p][i][] = f[p][i][] = -inf;

     if (first[p] == ) return;

     for (x = first[p]; x; x = e[x].next) {

         dfs(y);

         for (t1 = ; t1 < ; ++t1) {

             for (j = ; j < n; ++j) t[j] = f[p][j][t1];

             for (t2 = ; t2 < ; ++t2) {

                 tmp = t1 && t2 && p;

                 for (i = ; i < n; ++i) if (f[y][i][t2] != -inf)

                     for(j = n - ; i + tmp <= j; --j)

                         if (f[p][j - i - tmp][t1] != -inf)

                             t[j] = max(t[j], f[p][j - i - tmp][t1] + f[y][i][t2]);

             }

             for (j = ; j < n; ++j) f[p][j][t1] = max(f[p][j][t1], t[j]);

         }

     }

 }

 #undef y

 int main() {

     int i;

     scanf("%d%d", &n, &tar);

     for (i = ; i <= n; ++i) {

         scanf("%d%d", &tr[i].v, &tr[i].fa);

         add_edge(tr[i].fa, i);

     }

     dfs();

     for (ans = n - ; ~ans && f[][ans][] < tar; --ans);

     printf("%d\n", ans);

     return ;

 }