设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 + ;
int dp[maxn][][];
char str[ + ];
struct Edge {
int u, v, tonext;
} e[maxn * ];
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 = ; i <= n; ++i) {
printf("node %d: ", i);
for (int j = first[i]; ~j; j = e[j].tonext) {
printf("%d ", e[j].v);
}
printf("\n");
}
printf("***************\n");
}
vector<int> vc[maxn];
int d[maxn][];
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 < ) return -inf;
if (k == ) {
int sum = ;
for (int i = ; i <= n; ++i) sum += arr[i].a;
return sum;
}
if (n < k) return -inf;
memset(d, -0x3f, sizeof d);
d[][] = ;
for (int i = ; i <= n; ++i) {
for (int j = k; j >= ; --j) {
if (d[i - ][j] >= ) d[i][j] = max(d[i][j], d[i - ][j] + arr[i].a);
if (j >= && d[i - ][j - ] >= ) d[i][j] = max(d[i][j], d[i - ][j - ] + 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][][] += max(dp[v][][], dp[v][][]);
dp[cur][][] += max(dp[v][][], dp[v][][]); // 爸爸是黑色
}
int sel = , val = , to = ;
for (int i = ; i < vc[cur].size(); ++i) {
int v = vc[cur][i];
if (dp[v][][] >= ) {
arr[++to] = Node(dp[v][][], dp[v][][]);
} else {
sel++; //这些不能变成白色，也就是固定必须是黑色
val += dp[v][][]; //其贡献
}
}
dp[cur][][] = getMax(arr, to, k - - sel) + val;
dp[cur][][] = getMax(arr, to, k - sel) + val;
if (dp[cur][][] < ) dp[cur][][] = -;
else dp[cur][][]++;
if (dp[cur][][] < ) dp[cur][][] = -;
else dp[cur][][]++;
}
void work() {
num = ;
memset(in ,false, sizeof in);
memset(first, -, sizeof first);
memset(dp, -, sizeof dp);
memset(son, false, sizeof son);
scanf("%d%d", &n, &k);
for (int i = ; i <= maxn - ; ++i) vc[i].clear();
getchar();
for (int i = ; i <= n; ++i) {
gets(str + );
// printf("%s\n", str + 1);
int lenstr = strlen(str + );
for (int j = ; j <= lenstr;) {
if (str[j] >= '' && str[j] <= '') {
int fuck = str[j] - '';
++j;
while (j <= lenstr && str[j] >= '' && str[j] <= '') {
fuck = fuck * + str[j] - '';
++j;
}
if (fuck == ) break;
son[i]++;
addEdge(i, fuck);
in[fuck] = true;
} else j++;
}
}
int root = ;
for (int i = ; i <= n; ++i) {
if (!in[i]) {
root = i;
break;
}
}
// show();
if (n == ) {
if (k != ) {
printf("0\n");
return;
}
}
for (int i = ; i <= n; ++i) {
dp[i][][] = dp[i][][] = ;
}
if (k == ) {
printf("%d\n", n);
return;
}
if (k == ) {
for (int i = ; i <= n; ++i) {
if (!son[i]) {
dp[i][][] = ;
dp[i][][] = -;
dp[i][][] = ;
dp[i][][] = ;
}
}
}
dfs(root);
int ans = dp[root][][];
ans = max(ans, dp[root][][]);
ans = max(ans, dp[root][][]);
// ans = max(ans, dp[root][0][1]);
printf("%d\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}