题目描述

鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时他找不到解决问题的方法，这让他很伤心。

现在他有以下问题。

他必须保护一座中世纪城市，这条城市的道路构成了一棵树。

每个节点上的士兵可以观察到所有和这个点相连的边。

他必须在节点上放置最少数量的士兵，以便他们可以观察到所有的边。

你能帮助他吗？

例如，下面的树：

只需要放置 1 名士兵（在节点 1 处），就可观察到所有的边。

输入格式

输入包含多组测试数据，每组测试数据用以描述一棵树。

对于每组测试数据，第一行包含整数 $N$，表示树的节点数目。

接下来 $N$ 行，每行按如下方法描述一个节点。

节点编号：(子节点数目) 子节点 子节点 …

节点编号从 $0$ 到 $N-1$，每个节点的子节点数量均不超过 $10$，每个边在输入数据中只出现一次。

输出格式

对于每组测试数据，输出一个占据一行的结果，表示最少需要的士兵数。

样例

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

1
2

样例解释

第一组数据

$N = 4$ 树的结构：

0 -- 1
    / \
   2   3

节点 0 只有一个子节点 1。 节点 1 有两个子节点 2 和 3。 节点 2 和 3 是叶子节点。

最优方案：在节点 1 放置一个士兵，可以观察到所有边 (0-1, 1-2, 1-3)。 输出 1。

第二组数据

$N = 5$ 树的结构： 输入描述：

3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

即：

• 节点 3 有三个子节点：1, 4, 2
• 节点 1 有一个子节点：0
• 节点 2 是叶子
• 节点 0 是叶子
• 节点 4 是叶子

树的结构：

    3
  / | \
 1  4  2
 |
 0

最优方案：在节点 1 和节点 3 各放一个士兵（或者节点 1 和节点 2 等），可以覆盖所有边。 最少需要 2 个士兵，输出 2。

数据范围

• $0 < N \le 1500$
• 一个测试点所有 $N$ 相加之和不超过 300650（即多组数据总和不超过约 30 万节点）

算法分析

这是一个树的最小点覆盖问题（最小顶点覆盖），但略有不同：在经典的点覆盖中，要求每条边的至少一个端点被选中；而本题要求每个节点上的士兵可以观察到所有与该节点相连的边，即如果选中一个节点，它可以覆盖所有与该节点相邻的边。这实际上就是最小点覆盖。

对于树来说，最小点覆盖可以用树形动态规划解决。

状态定义

设 $dp[u][0]$ 表示以 $u$ 为根的子树中，不在节点 $u$ 放置士兵的情况下，覆盖该子树所有边需要的最少士兵数。 设 $dp[u][1]$ 表示在节点 $u$ 放置士兵的情况下，覆盖该子树所有边需要的最少士兵数。

转移方程

对于节点 $u$，设其子节点集合为 $children(u)$。

1. 如果 $u$ 不放置士兵（$dp[u][0]$），那么它的所有子节点 $v$ 都必须放置士兵，因为边 $(u,v)$ 必须被覆盖（$u$ 没士兵，只能靠 $v$ 来覆盖这条边）。所以：

   $$dp[u][0] = \sum_{v \in children(u)} dp[v][1]$$

2. 如果 $u$ 放置士兵（$dp[u][1]$），那么它的子节点 $v$ 可以放也可以不放士兵（因为边 $(u,v)$ 已经被 $u$ 覆盖了）。所以：

   $$dp[u][1] = 1 + \sum_{v \in children(u)} \min(dp[v][0], dp[v][1])$$

   其中 $+1$ 是因为在 $u$ 放置了一个士兵。

初始化

对于叶子节点 $u$：

• $dp[u][0] = 0$（不放士兵，没有边需要覆盖？但叶子节点有一条边连向父节点，如果叶子不放士兵，那么这条边需要父节点覆盖，所以对于叶子节点，$dp[u][0]$ 从转移方程看是求和子节点，叶子没有子节点，所以为 0，这是合理的，因为叶子不放士兵时，覆盖该子树（只有自己）所需士兵数为 0，但边 $(u, parent)$ 的覆盖由父节点负责。）
• $dp[u][1] = 1$（放一个士兵）

最终答案

整棵树的最小点覆盖为 $\min(dp[root][0], dp[root][1])$，其中 $root$ 是树的根节点（可以任选，比如 0 号节点）。

注意：对于根节点，如果它不放士兵，那么它的所有子节点必须放士兵，这已经在转移中考虑。

树的建立

输入给出了每个节点的子节点，但实际上是无向树，每条边只出现一次，所以输入中的“子节点”只是表示与它相邻的节点（因为树是无向的）。我们需要建立无向图，然后任选一个根（比如 0）进行 DFS。

细节

• 多组数据，需要重置数组。
• 节点编号从 0 到 N-1。
• 每个节点的子节点数不超过 10，但总节点数可达 1500，所以 DFS 递归深度可能较大，需要防止栈溢出（可以用迭代栈或增大栈空间）。
• 注意输入格式：每行形如 u:(k) v1 v2 ... vk，可能有空格，需要正确解析。

复杂度

• 每个节点访问一次，转移复杂度与子节点数成正比，总复杂度 $O(N)$。
• 多组数据总复杂度 $O(\sum N)$，可以接受。

样例验证

第一组数据

树：0-1-2, 0-1-3

以 0 为根：

• 节点 2 和 3 是叶子：$dp[2][0]=0, dp[2][1]=1$；$dp[3][0]=0, dp[3][1]=1$
• 节点 1（子节点 2 和 3）： $dp[1][0] = dp[2][1] + dp[3][1] = 1+1=2$ $dp[1][1] = 1 + \min(dp[2][0],dp[2][1]) + \min(dp[3][0],dp[3][1]) = 1 + (0) + (0) = 1$
• 节点 0（子节点 1）： $dp[0][0] = dp[1][1] = 1$ $dp[0][1] = 1 + \min(dp[1][0],dp[1][1]) = 1 + \min(2,1) = 1+1=2$

答案 $\min(dp[0][0], dp[0][1]) = \min(1,2)=1$，正确。

第二组数据

树：3 为根，子节点 1,4,2；节点 1 有子节点 0。

以 3 为根：

• 叶子节点 0,2,4：$dp=0,1$
• 节点 1（子节点 0）： $dp[1][0] = dp[0][1] = 1$ $dp[1][1] = 1 + \min(dp[0][0],dp[0][1]) = 1+0=1$
• 节点 3（子节点 1,4,2）： $dp[3][0] = dp[1][1] + dp[4][1] + dp[2][1] = 1+1+1=3$ $dp[3][1] = 1 + \min(dp[1][0],dp[1][1]) + \min(dp[4][0],dp[4][1]) + \min(dp[2][0],dp[2][1]) = 1 + \min(1,1) + \min(0,1) + \min(0,1) = 1+1+0+0=2$

答案 $\min(3,2)=2$，正确。

实现提示

• 使用邻接表存树。
• DFS 时传入父节点参数，避免重复访问。
• 注意多组数据的初始化。