Leaf Nodes in a Tree

Interview

Time limit2sMemory limit128 MB

Summary

Given a tree by parent array, delete a node and all its descendants, then count how many leaf nodes remain.

Level: Easy3 of 10
Topics: Tree, DFS, Implementation
Solved: No attempts yet

Problem

A leaf node is a node with no children.

You are given a tree. When one node is deleted, that node and all of its descendants disappear from the tree. Find the number of leaf nodes remaining after deleting the specified node.

The tree below has 3 leaf nodes. The nodes colored green are leaf nodes.

If node 1 is deleted from this tree, node 1 and its descendants are removed together. The nodes colored black are the deleted nodes.

In this case, the remaining tree has 1 leaf node.

Input

The first line contains the number of nodes N. N is a positive integer no greater than 50.

The second line contains the parent of each node from node 0 through node N-1, in order. For the root node, which has no parent, the value is -1.

The third line contains the number of the node to delete.

Output

Print the number of leaf nodes remaining after deleting the specified node.

Examples4

Example 1
Input
```
5
-1 0 0 1 1
2
```
Expected output
```
2
```
Example 2
Input
```
5
-1 0 0 1 1
1
```
Expected output
```
1
```
Example 3
Input
```
5
-1 0 0 1 1
0
```
Expected output
```
0
```
Example 4
Input
```
9
-1 0 0 2 2 4 4 6 6
4
```
Expected output
```
2
```