题目描述

FIPA（国际国际计划协会联合会）近期将进行投票，以确定下一届 IPWC（国际规划世界杯）的主办方。

钻石大陆的代表本内特希望通过以赠送钻石买通国家的方式，获得更多的投票。

当然，他并不需要买通所有的国家，因为小国家会跟随着他们附庸的大国进行投票。

换句话说，只要买通了一个大国，就等于获得了它和它统治下所有小国的投票。

例如，C 在 B 的统治下，B 在 A 的统治下，那么买通 A 就等于获得了三国的投票。

请注意，一个国家最多附庸于一个国家的统治下，附庸关系也不会构成环。

请你编写一个程序，帮助本内特求出在至少获得 m 个国家支持的情况下的最少花费是多少。

输入格式

输入包含多组测试数据。

第一行包含两个整数 n 和 m，其中 n 表示参与投票的国家的总数，m 表示获得的票数。

接下来 n 行，每行包含一个国家的信息，形式如下：

CountryName DiamondCount DCName DCName ...

其中 CountryName 是一个长度不超过 100 的字符串，表示这个国家的名字，DiamondCount 是一个整数，表示买通该国家需要的钻石数，DCName 是一个字符串，表示直接附庸于该国家的一个国家的名字。

一个国家可能没有任何附庸国家。

当读入一行为 # 时，表示输入终止。

输出格式

每组数据输出一个结果，每个结果占一行。

样例

3 2
Aland 10
Boland 20 Aland
Coland 15
#

20

样例解释

输入

• $n=3$，$m=2$（需要至少获得 2 个国家的支持）
• 国家信息：
  1. Aland 10：国家 Aland，买通需要 10 钻石，没有附庸国家。
  2. Boland 20 Aland：国家 Boland，买通需要 20 钻石，附庸于 Aland（即 Aland 统治 Boland）。
  3. Coland 15：国家 Coland，买通需要 15 钻石，没有附庸国家。

附庸关系

Aland 统治 Boland，Coland 独立。

目标

至少获得 2 个国家的支持（即控制至少 2 个国家）。

方案

1. 买通 Aland：花费 10，获得 Aland 和 Boland 的支持（共 2 个国家），满足条件。
2. 买通 Coland 和 Boland：花费 15+20=35，获得 Coland 和 Boland（共 2 个），但花费更多。
3. 买通 Boland：花费 20，获得 Boland（只有 1 个），不满足至少 2 个。
4. 买通 Coland：花费 15，获得 Coland（只有 1 个），不满足。
5. 买通 Aland 和 Coland：花费 10+15=25，获得 Aland、Boland、Coland（共 3 个），花费 25 > 10。

所以最小花费是 10？但样例输出是 20，说明我们的理解有误。

仔细读题：“买通了一个大国，就等于获得了它和它统治下所有小国的投票。” 这意味着如果买通 Aland，就获得了 Aland 和 Boland 的投票，共 2 票。花费 10，应该满足条件且花费最小。为什么样例输出是 20？

可能题目中“至少获得 m 个国家支持”是指直接或间接控制的国家数量至少为 m，而不是投票数？但这里国家数量就是投票数。那为什么输出 20？

检查输入格式：第一行是 n m，接着 n 行。样例输入中，第一行 3 2，接着三行国家信息。但是第三行 Coland 15 后面没有附庸国家，所以 Coland 是独立的。

那么为什么最优解是 20 而不是 10？也许附庸关系是反的：Boland 20 Aland 表示 Boland 的附庸是 Aland？即 Aland 是 Boland 的附庸？但描述是“DCName 表示直接附庸于该国家的一个国家的名字”，所以 Boland 的附庸是 Aland，即 Aland 附庸于 Boland。

重新解释：Boland 20 Aland 表示国家 Boland，买通花费 20，它的一个直接附庸是 Aland。即 Boland 统治 Aland。

那么附庸关系：Boland 统治 Aland，Coland 独立。

现在考虑：

• 买通 Boland：花费 20，获得 Boland 和 Aland 的支持（共 2 个国家），满足条件。
• 买通 Aland：花费 10，只获得 Aland（1 个），不满足。
• 买通 Coland：花费 15，只获得 Coland（1 个），不满足。
• 买通 Boland 和 Coland：花费 20+15=35，获得 3 个，但花费更多。

所以最小花费是 20，与样例输出一致。

因此，正确理解是：每行中，DCName 是该国家的直接附庸，即该国家统治 DCName。

数据范围

• $1 \le n \le 200$
• $0 \le m \le n$

算法分析

这是一个树形依赖背包问题。

问题转化

国家之间的附庸关系构成一棵森林（因为每个国家最多附庸于一个国家，且无环）。我们可以建立一个虚拟根节点 0，将所有树的根连接到虚拟根上，形成一棵树。

买通一个国家，就获得了它以及它子树中所有国家的支持（即控制这些国家）。

我们需要选择若干个节点（国家）买通，使得被控制的节点总数至少为 $m$，并且买通花费最小。

注意：如果买通一个节点，那么它的所有子孙节点自动被控制，不需要再买通。

树形 DP

设 $dp[u][j]$ 表示在以 $u$ 为根的子树中，控制恰好 $j$ 个节点（包括 $u$ 自身及其子孙）所需的最小花费。

转移时，考虑节点 $u$ 是否被买通：

1. 买通 $u$：花费 $cost[u]$，那么 $u$ 的所有子孙节点自动被控制，因此 $u$ 的子树中控制节点数至少为 $size[u]$（$size[u]$ 是以 $u$ 为根的子树节点数）。但我们可以选择不控制所有子孙？实际上，买通 $u$ 后，所有子孙自动被控制，无法选择不控制某些子孙。所以如果买通 $u$，那么 $dp[u][size[u]] = cost[u]$。

   更一般地，如果买通 $u$，那么我们可以再考虑在 $u$ 的各个子树中不再额外买通任何节点（因为已经全部控制了），所以 $dp[u][size[u]] = cost[u]$。

   但如果我们买通 $u$ 后，还想在某些子树中额外买通一些节点（以获得更多控制？但已经全部控制了，额外买通不会增加控制数，只会增加花费，所以不会这样做）。因此，买通 $u$ 时，只控制 $size[u]$ 个节点，花费 $cost[u]$。

2. 不买通 $u$：那么 $u$ 本身不被控制，我们需要在 $u$ 的各个子树中选择买通一些节点，使得控制的节点总数达到 $j$（注意 $j$ 不包括 $u$ 本身）。这变成了一个分组背包问题：每个子树是一个组，每组可以选择控制 $0 \sim size[v]$ 个节点（$v$ 是子节点），花费为 $dp[v][k]$。我们需要从每组中选择一个方案，使得总控制节点数之和为 $j$，且总花费最小。

   转移方程：

   $$dp[u][j] = \min \left\{ \sum_{v \in children(u)} dp[v][k_v] \right\}, \quad \text{满足} \sum_{v} k_v = j$$

   这可以用分组背包 DP 实现。

初始化

• 对于叶子节点 $u$：$size[u]=1$。
  • 买通 $u$：$dp[u][1] = cost[u]$
  • 不买通 $u$：$dp[u][0] = 0$
• 其他 $dp[u][j] = \infty$

最终答案

考虑虚拟根节点 0，其花费 $cost[0]=0$，且不买通它（因为买通虚拟根没有意义）。那么答案就是 $dp[0][j]$ 中满足 $j \ge m$ 的最小值。

注意：由于题目要求“至少获得 m 个国家支持”，所以控制节点数可以大于 m，取最小值即可。

复杂度

状态数 $O(n^2)$，每个节点的转移需要枚举子节点和容量，总复杂度 $O(n^3)$，$n \le 200$，$200^3 = 8\times10^6$，可以接受。

实现细节

• 需要将国家名字映射到编号。
• 建立树时，根据输入确定父子关系。注意输入中每行的 DCName 是 $u$ 的直接附庸，即 $u$ 是父节点，DCName 是子节点。
• 虚拟根节点 0 连接所有没有父节点的国家。
• 树形 DP 使用后序遍历。
• 注意 $dp$ 数组初始化为无穷大，使用 long long 或足够大的整数。

样例验证

样例数据

$n=3, m=2$ 国家：

1. Aland: cost=10，没有附庸（即子节点）
2. Boland: cost=20，附庸 Aland（即 Boland 是父节点，Aland 是子节点）
3. Coland: cost=15，没有附庸

建立树：

• 虚拟根 0
• 子节点：Boland, Coland（因为 Aland 有父节点 Boland，所以不是根）
• Boland 的子节点：Aland

节点编号：0(虚拟根), 1(Boland), 2(Coland), 3(Aland)

树形 DP

叶子节点 3 (Aland)：

• $dp[3][0] = 0$
• $dp[3][1] = 10$（买通）

节点 1 (Boland)： 子节点：3 (Aland) $size[1] = 1 + size[3] = 2$

不买通 1：

• 从子节点 3 中选择控制 $k$ 个节点：
  • $k=0$：$dp[1][0] = dp[3][0] = 0$
  • $k=1$：$dp[1][1] = dp[3][1] = 10$
  • $k=2$：不可能，因为子节点最多控制 1 个节点，加上自己？但不买通时自己不算，所以最多 1 个。

买通 1：$dp[1][2] = 20$

因此 $dp[1][0]=0, dp[1][1]=10, dp[1][2]=20$

节点 2 (Coland)：叶子，$dp[2][0]=0, dp[2][1]=15$

虚拟根 0： 子节点：1, 2 $size[0] = 1 + size[1] + size[2] = 1+2+1=4$

不买通 0（虚拟根总是买通？不，虚拟根不买通）： 分组背包：

• 子节点 1：可选控制 0,1,2 个节点，花费分别为 0,10,20
• 子节点 2：可选控制 0,1 个节点，花费分别为 0,15

组合：

• 控制 0 个：0+0=0
• 控制 1 个：min(0+15, 10+0)=10
• 控制 2 个：min(0+20, 10+15, 20+0)=20
• 控制 3 个：10+20=30
• 控制 4 个：20+15=35

所以 $dp[0][0]=0, dp[0][1]=10, dp[0][2]=20, dp[0][3]=30, dp[0][4]=35$

需要至少 $m=2$ 个节点支持，所以 $j\ge2$ 的最小花费是 $dp[0][2]=20$。

输出 20，符合样例。

总结

本题是树形 DP 中的依赖背包问题，关键点在于：

1. 建立虚拟根将森林转为树。
2. 状态定义：$dp[u][j]$ 表示以 $u$ 为根的子树中控制恰好 $j$ 个节点的最小花费。
3. 转移分买通和不买通两种情况，不买通时使用分组背包合并子节点。