练习 6：树上最小覆盖集

题目描述：

给定一棵以 1 为根的有根树。现在要选择最少的结点，使得每条边至少有一个端点被选中。问最少需要选择多少个结点？

输入格式：

• 第一行：一个正整数 n（2 ≤ n ≤ 1000）
• 第二行：n-1 个正整数 f_2, f_3, ..., f_n，其中 f_i 表示结点 i 的父结点编号

输出格式：

• 一行，一个整数，表示最少需要选择的结点数

样例输入：

5
1 1 2 2

样例输出：

2

样例解释：

选择结点 1, 2 或 1, 3 都可以覆盖所有边。

提示：

• 树形 DP：dp[u][0] 表示不选 u 时，u 子树最少选几个（此时必须选所有子结点）
• dp[u][1] 表示选 u 时，u 子树最少选几个（子结点可选可不选）
• 转移：
  • dp[u][0] = 1 + sum(dp[v][1])
  • dp[u][1] = 1 + sum(min(dp[v][0], dp[v][1]))