Description
related problem : 12574 - New Year
Alice is a grownup. She thinks New Year is a tradition that involves many troublesome events such as family reunion, etc. Even worse, there is always one event that can despair her - giving red envelopes to relatives( a.k.a. people in your family whom you will only meet once a year ).
Her family tree looks like this. Alice has to give red envelopes to relatives marked in red circles.
Since Alice is a grownup who is expected to be kind, mature, showing respect to the elderlies, and showing care to the younger generations. She is giving red envelopes to :
-
1 for parents, 1 for grandparents, 1 for grand-grand-parents, 1 for grand-...-grandparents
-
1 for each of siblings' children
-
1 for each of children, children's children, children's children's children, children's ... children's children
Therefore, the version "New Year Family Tree" for Alice looks like the following graph. Relatives marked with red nodes in the "New Year Family Tree" are whom Alice has to give red envelopes to.
Alice has a large family, she has to give many red envelopes in New Year's Eve. Given Alice's "New Year Family Tree", please tell Alice how many red envelopes she is going to give.
Maybe Useful Hints - 1
In the previous 12574 - New Year, you learned to find who will give red envelopes to a specific person.
Try to find for each person, whether Alice will give a red envelope to him/her.
Maybe Useful Hints - 2
Q : How to count the number of "children, children's children, children's children's children, children's ... children's children" in a faster way?
A : Recursion may be a good approach
Consider this simple family tree : Let f(x) be the number of people in family tree x
Input
The input is in the following format :
N P1 P2 P3 ... PN
-
N is an integer which means there are N people in the "New Year Family Tree" (including Alice). People are numbered from 1 to N. Alice is numbered with N.
-
There are N integers in the second line. Pi (the i-th number counted from the left) is the parent of person i. If Pi = -1, it means that person i 's parent is too old and has passed away.
Technical Restrictions
-
1 <= N <= 10^5
-
1 <= Pi <= N or Pi = -1
-
Only the oldest grand-...-grandparents has passed away in the "New Year Family Tree"
-
Each person has at most 5 children
Test Case
-
Test 1 : n <= 100, can be passed using hint 1
-
Test 2 - 3 : n <= 2000, can be passed using hint 1
-
Test 4 - 6 : n <= 100000, can be passed using hint 2
Output
Output how many red envelopes Alice will give. Remember to add a newline character in the end.