J. 树的最小点覆盖

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一颗 $n$ 个节点 $n-1$ 条边的树，树的根为 $1$ 。

请你从中选择尽量少的节点，使得每一条边至少有一个端点被选中。请你求出这个最小的选择点数。

第一行包含一个整数 $n$ （ $2 \leq n \leq 10^5$ ），表示树的节点数。

第二行 $n-1$ 个整数 $f_2, f_3, \dots, f_n$ ，其中 $f_i$ 表示第 $i$ 号节点的直接父节点编号（ $1 \le f_i < i$ ）。

输出一个整数，表示最小的选择点数。

5
1 2 3 1

蓝桥杯国赛训练