g6-07506. 哨塔覆盖·最少选点

题目描述

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。选择尽量少的结点，使得每个结点要么自己被选，要么它的某个相邻结点被选。

输出最少需要选择的结点数。

第一行一个整数 $n$ 。

第二行 $n - 1$ 个整数 $f_{2}, f_{3}, \dots, f_{n}$ ，其中 $f_{i}$ 表示结点 $i$ 的父亲，保证 $f_{i} < i$ （ $n = 1$ 时该行为空）。

一行一个整数，表示最少选择的结点数。

输入：

4
1 2 3

输出：

链 $1 - 2 - 3 - 4$ ：选 $2$ 与 $4$ ，四个点全部被覆盖，共 $2$ 个。

输入：

4
1 1 1

输出：

星形：只选 $1$ 号，四个点全部被覆盖。