레이팅 미적용SWERC organizers want to hold a gastronomic event. The location of the event is a building with \(n\) rooms connected by \(n - 1\) corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room. In each room you have to set up the tasting of a typical Italian dish. You can choose from \(n\) typical Italian dishes rated from 1 to \(n\) depending on how good they are (\(n\) is the best possible rating). The \(n\) dishes have distinct ratings. You want to assign the \(n\) dishes to the \(n\) rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that: • Each room in the sequence is connected to the next one in the sequence by a corridor. • The ratings of the dishes in the rooms (in the order given by the sequence) are increasing. If you assign the \(n\) dishes optimally, what is the maximum number of pleasing tours?
The first line contains an integer \(n\) (\(2 \le n \le 1\,000\,000\)) — the number of rooms. The second line contains \(n - 1\) integers \(p_{2}\), \(p_{3}\), · · · , \(p_{n}\) (\(1 \le p_{i} < i\)). Each \(p_{i}\) indicates that there is a corridor between room \(i\) and room \(p_{i}\). It is guaranteed that the building has the property that it is possible to go from any room to any other room.
Print the maximum number of pleasing tours.
5
1 2 2 2
13
10
1 2 3 4 3 2 7 8 7
47