P2279 [HNOI2003] Establishing Fire Stations

In 2020, humans established a large cluster of bases on Mars, with a total of $n$ bases. To save materials at the beginning, humans built only $n-1$ roads to connect these bases, and every pair of bases can be reached via roads, so all the bases form a large tree structure. If traveling from base A to base B requires at least $d$ roads (i.e., the length of the shortest path is $d$), we define the distance from base A to base B to be $d$. Because Mars is very dry and fires occur frequently, humans decided to build several fire stations. Fire stations can only be built in bases, and each fire station can extinguish fires at any base whose distance from it does not exceed $2$. Your task is to compute the minimum number of fire stations needed to ensure that whenever a fire occurs at any base on Mars, the firefighters can extinguish it in time.

The first line contains $n$ ($1 \leq n \leq 1000$), the number of bases on Mars. For each $i = 2, 3, \dots, n$, line $i$ contains a positive integer $a_i$, indicating that there is a road between base $i$ and base $a_i$. To make the tree representation concise, $a_i < i$.

Output a single positive integer, the minimum number of fire stations required so that any base that catches fire can be extinguished in time.

Translated by ChatGPT 5