消防局的设立(Fire Stations)

题目描述

2020 年，人类在火星上建立了一个庞大的基地群，总共有 $n$ 个基地。起初为了节约材料，人类只修建了 $n-1$ 条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地 $A$ 到基地 $B$ 至少要经过 $d$ 条道路的话，我们称基地 $A$ 到基地 $B$ 的距离为 $d$。

由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过 $2$ 的基地的火灾。

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。

输入格式

输入文件的第一行为 $n$（$1 \leq n \leq 1000$），表示火星上基地的数目。接下来的 $n-1$ 行每行有一个正整数，其中文件第 $i$ 行的正整数为 $a_i$，表示从编号为 $i$ 的基地到编号为 $a_i$ 的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有 $a_i\lt i$。

输出格式

仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

样例输入 #1

6
1
2
3
4
5

样例输出 #1

2

数据范围

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a_i < i$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接