Tree
InterviewTime limit2sMemory limit1024 MB
Count the red and green colorings of a rooted tree's edges where each vertex has at most one red edge from its children, modulo 10^9 + 7.
- Level
Medium4 of 10
- Topics
- Tree, Dynamic programming
- Solved
- No attempts yet
Problem
A painter lives in a small kingdom and creates art in his free time. He is very talented, and his trees are especially good. The queen likes his paintings so much that she hung one of his tree pictures in her room.
Word has reached the kingdom that an exhibition of paintings will be held soon. Kings and queens of other kingdoms value the countries with talented painters, visit each other's castles often, and work closely together. So the queen decided to send one of the painter's works to the exhibition. The kingdom is small, so the painter cannot afford colored paints, and all his pictures are black and white. The queen wants her kingdom's painting to stand out, so she ordered the court apothecary to make two paint colors: red and green, the colors of the kingdom's flag. Once the paints were ready, the painter became interested in another question: how to color his tree.
For each edge of the tree, he chooses one of the two colors and paints the edge with it. The queen only likes trees colored in an interesting way. A coloring is interesting if every vertex has at most one red edge coming to it from its children.
The painter wants his coloring to be interesting so that he is not punished. But one tree can have many colorings, and he has trouble choosing among them. Help him count how many different interesting colorings the tree has.
Since the count can be large, output it modulo .
Input
The first line contains , the number of vertices in the tree ().
The second line contains integers. The -th of them is , the parent of vertex . The root is always vertex .
Output
Print one integer, the number of interesting colorings of the tree modulo .