1722: [Usaco2006 Mar] Milk Team Select 产奶比赛

https://www.lydsy.com/JudgeOnline/problem.php?id=1722
分析：
　　f[u][i][0/1]表示子树u中，有i对相邻的点，最大和是多少。
代码：
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 using namespace std;
14 typedef long long LL;
15 
16 inline int read() {
17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
19 }
20 
21 const int N = 1005;
22 const int INF = 1e9;
23 
24 int f[N][N][2], g[N][2];
25 int head[N], nxt[N], to[N], siz[N], w[N], fa[N];
26 int n, x, En;
27 
28 void add_edge(int u,int v) {
29     ++En; to[En] = v; nxt[En] = head[u]; head[u] = En; 
30 }
31 
32 void dfs(int u) {
33     siz[u] = 1;
34     f[u][0][1] = w[u];
35     f[u][0][0] = 0;
36     for (int i=head[u]; i; i=nxt[i]) {
37         int v = to[i];
38         dfs(v);
39         siz[u] += siz[v];
40         for (int j=0; j<=siz[u]-1; ++j) // 相邻的 
41             for (int k=0,lim=min(j, siz[v]-1); k<=lim; ++k) { // 子树中相邻的 
42                 g[j][0] = max(g[j][0], f[u][j - k][0] + max(f[v][k][1], f[v][k][0]));//cerr << g[j][0] << "
";
43                 if (j - k >= 0) g[j][1] = max(g[j][1], f[u][j - k][1] + f[v][k][0]); //cerr << g[j][1] << "
";;
44                 if (j - k - 1 >= 0) g[j][1] = max(g[j][1], f[u][j - k - 1][1] + f[v][k][1]);// cerr << g[j][1] << "
";;
45                 
46             }
47         for (int j=n; j>=0; --j) 
48             f[u][j][0] = g[j][0], f[u][j][1] = g[j][1], g[j][0] = g[j][1] = -INF;
49     }
50 }
51 int main() {
52     n = read(), x = read();
53     memset(f, -0x3f, sizeof(f));
54     memset(g, -0x3f, sizeof(g)); // 把g[0]初始化了！！！ 
55 //    for (int i=1; i<=n; ++i) g[i][0] = g[i][1] = -INF;
56     for (int i=1; i<=n; ++i) {
57         w[i] = read(), fa[i] = read();
58         add_edge(fa[i], i);
59     }
60     dfs(0);
61     for (int i=n; i>=0; --i) {
62         if (f[0][i][0] >= x) { cout << i; return 0; }
63     }
64     cout << -1;
65     return 0;
66 }