设dp[cur][i][j]表示当前是第cur个顶点，自身状态是i（0或者1），爸爸的状态是j（0或者1）的时候的最多白色节点数。
0---白色
1---黑色
如果不合法，就是第cur号顶点不能染成白色，则为-1，注意到任意节点都可以染成黑色，所以dp[cur][1][0] = dp[cur][1][1] = 0
转移：
首先把叶子节点特判掉，因为叶子节点的状态很容易判断，并且只有k == 1的时候，才有dp[left][0][1] = 1
然后留给每一个爸爸的转移就是：
1、如果爸爸染黑色，则从 dp[son][1][1]和dp[son][0][1]娶个max过来即可。
2、比较麻烦的是爸爸染了白色。这样就相当于对于所有的儿子（儿子的状态已经全部算出来了），把k个染成黑色（使得爸爸合法），剩下的染成白色，使得白色节点数最大，
也就是给出一个结构体数组，有arr[i].a和arr[i].b表示这个节点染成白色，得到arr[i].a贡献，这个节点染成黑色，得到arr[i].b贡献。
设d[n][k]表示前n个物品，确定选了k个做黑色的最大贡献。二维费用背包转移即可。hack: 需要用到d[i][0]
所以d[0][0] = 0，而d[1][0] = arr[1].a d[2][0] = arr[1].a + arr[2].a
这题写那个二维费用dp的时候坑队友了，没写出来，转移的时候没考虑d[i][0]
#include <bits/stdc++.h> #include <algorithm> #define inf (0x3f3f3f3f) using namespace std; typedef long long int LL; const int maxn = 1e2 + 20; int dp[maxn][2][2]; char str[1000000 + 2]; struct Edge { int u, v, tonext; } e[maxn * 2]; int first[maxn], num; void addEdge(int u, int v) { e[num].u = u, e[num].v = v, e[num].tonext = first[u]; first[u] = num++; } int son[maxn]; bool in[maxn]; int n, k; void show() { for (int i = 1; i <= n; ++i) { printf("node %d: ", i); for (int j = first[i]; ~j; j = e[j].tonext) { printf("%d ", e[j].v); } printf(" "); } printf("*************** "); } vector<int> vc[maxn]; int d[maxn][20]; struct Node { int a, b; Node(int _a, int _b) { a = _a, b = _b; } Node() {} } arr[maxn]; int getMax(struct Node arr[], int n, int k) { if (k < 0) return -inf; if (k == 0) { int sum = 0; for (int i = 1; i <= n; ++i) sum += arr[i].a; return sum; } if (n < k) return -inf; memset(d, -0x3f, sizeof d); d[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = k; j >= 0; --j) { if (d[i - 1][j] >= 0) d[i][j] = max(d[i][j], d[i - 1][j] + arr[i].a); if (j >= 1 && d[i - 1][j - 1] >= 0) d[i][j] = max(d[i][j], d[i - 1][j - 1] + arr[i].b); } } return d[n][k]; } void dfs(int cur) { if (!son[cur]) return; for (int i = first[cur]; ~i; i = e[i].tonext) { int v = e[i].v; vc[cur].push_back(v); dfs(v); dp[cur][1][0] += max(dp[v][0][1], dp[v][1][1]); dp[cur][1][1] += max(dp[v][0][1], dp[v][1][1]); // 爸爸是黑色 } int sel = 0, val = 0, to = 0; for (int i = 0; i < vc[cur].size(); ++i) { int v = vc[cur][i]; if (dp[v][0][0] >= 0) { arr[++to] = Node(dp[v][0][0], dp[v][1][0]); } else { sel++; //这些不能变成白色，也就是固定必须是黑色 val += dp[v][1][0]; //其贡献 } } dp[cur][0][1] = getMax(arr, to, k - 1 - sel) + val; dp[cur][0][0] = getMax(arr, to, k - sel) + val; if (dp[cur][0][1] < 0) dp[cur][0][1] = -1; else dp[cur][0][1]++; if (dp[cur][0][0] < 0) dp[cur][0][0] = -1; else dp[cur][0][0]++; } void work() { num = 0; memset(in ,false, sizeof in); memset(first, -1, sizeof first); memset(dp, -1, sizeof dp); memset(son, false, sizeof son); scanf("%d%d", &n, &k); for (int i = 0; i <= maxn - 20; ++i) vc[i].clear(); getchar(); for (int i = 1; i <= n; ++i) { gets(str + 1); // printf("%s ", str + 1); int lenstr = strlen(str + 1); for (int j = 1; j <= lenstr;) { if (str[j] >= '0' && str[j] <= '9') { int fuck = str[j] - '0'; ++j; while (j <= lenstr && str[j] >= '0' && str[j] <= '9') { fuck = fuck * 10 + str[j] - '0'; ++j; } if (fuck == 0) break; son[i]++; addEdge(i, fuck); in[fuck] = true; } else j++; } } int root = 0; for (int i = 1; i <= n; ++i) { if (!in[i]) { root = i; break; } } // show(); if (n == 1) { if (k != 0) { printf("0 "); return; } } for (int i = 1; i <= n; ++i) { dp[i][1][0] = dp[i][1][1] = 0; } if (k == 0) { printf("%d ", n); return; } if (k == 1) { for (int i = 1; i <= n; ++i) { if (!son[i]) { dp[i][0][1] = 1; dp[i][0][0] = -1; dp[i][1][0] = 0; dp[i][1][1] = 0; } } } dfs(root); int ans = dp[root][0][0]; ans = max(ans, dp[root][1][1]); ans = max(ans, dp[root][1][0]); // ans = max(ans, dp[root][0][1]); printf("%d ", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }