### Problem Statement

Note to plugin users: There is an image in this problem statement. Please use the applet to view it.

An insertion into an immutable binary search tree does not alter the existing tree. Rather, it creates a new tree that contains the new value. For example, if a tree contains the values 1, 2, and 3, and you insert the value 4, then the new tree contains the values 1, 2, 3, and 4, but the old tree still exists and still contains only the values 1, 2, and 3. You could next insert, say, 5 into the new tree (obtaining a tree containing 1, 2, 3, 4, and 5) or into the old tree (obtaining a tree containing 1, 2, 3, and 5).

The simplest technique for implementing insertion into an immutable tree is called path-copying, because the entire path from the root to the site of the insertion is copied. Nodes not on this path are shared by the two trees. For example, if we insert 6 into the tree on the left in the picture below, we get the tree on the right. Notice that the nodes containing 3 and 5 were copied, but that the nodes containing 1, 2, and 4 are members of both trees. Even though the two trees contain a total of 11 elements, those elements are represented using only 8 nodes.

If we start with an empty tree and perform N insertions, then we end up with a total of N non-empty trees. However, some of those trees may now be garbage, meaning that they are no longer needed and can be deallocated. When we deallocate a tree, we deallocate all of its nodes, except for those nodes that also belong to trees that are not garbage. You must determine how many nodes remain after deallocating all nodes that can be deallocated.

A series of insertions is represented by a int[] values and a int[] trees. Let N be the number of insertions that are performed. The insertions are numbered from 0 to N-1. Insertion number I is specified by element I of values and element I of trees. Element I of values is the value that is inserted during the insertion, and element I of trees is the number of the tree that the value is inserted into, where tree number J is the result of insertion number J. If element I of trees is -1, then the value is inserted into the empty tree.

For example, the inputs

```     values = {  8,  6,  4,  7,  9,  1 }
trees  = { -1,  0,  1,  0, -1,  2 }
```
correspond to the following series of insertions:
```     tree0 = insert(8,empty)
tree1 = insert(6,tree0)
tree2 = insert(4,tree1)
tree3 = insert(7,tree0)
tree4 = insert(9,empty)
tree5 = insert(1,tree2)
```

The int[] garbage contains the numbers of the trees that are to be deallocated. In the example above, if garbage = {3,1,5}, then tree3, tree1, and tree5 are deallocated, but tree0, tree2, and tree4 are not. You should return the total number of nodes that remain after the garbage trees have been deallocated.

### Definition

 Class: ImmutableTrees Method: numNodes Parameters: int[], int[], int[] Returns: int Method signature: int numNodes(int[] values, int[] trees, int[] garbage) (be sure your method is public)

### Constraints

-values contains between 1 and 50 elements, inclusive.
-trees contains the same number of elements as values.
-Each element of values is between 1 and 1000, inclusive.
-values contains no duplicate elements.
-Element I of trees is between -1 and I-1, inclusive.
-garbage contains between 0 and N elements, inclusive, where N is the number of elements in values.
-Each element of garbage is between 0 and N-1, inclusive.
-garbage contains no duplicate elements.

### Examples

0)

 `{ 3, 2, 5, 4, 1, 6 }` `{-1, 0, 1, 2, 3, 4 }` `{ 0, 1, 2, 3 }`
`Returns: 8`
 The first example above.
1)

 `{ 8, 6, 4, 7, 9, 1 }` `{-1, 0, 1, 0,-1, 2 }` `{ 3, 1, 5}`
`Returns: 5`
 The second example above.
2)

 `{ 1, 2, 3, 4 }` `{-1, 0, 1, 0 }` `{ 0, 1, 2, 3 }`
`Returns: 0`
 Everything is garbage.
3)

 `{ 61,67,46,42,38,11,88,33,9,20,31,68,48,17,74,91,15,62,21,73 }` `{ -1,0,0,2,3,3,-1,6,5,4,2,0,10,0,0,8,3,10,6,12 }` `{ 17,11,18,1,10,12,2,6,0,4 }`
`Returns: 34`
4)

 `{ 37,12,11,7,10,36,17,19,18,23,8,31,32,15,21,4,25,33,29,22,5,3,34,20,13,30,1,35,2,9,14,27,28,16,24 }` `{ -1,0,1,2,3,3,3,2,-1,1,0,5,11,1,4,12,3,15,6,12,4,13,19,1,0,14,7,12,18,12,3,26,21,29,24 }` `{ 13,14,6,31,9,30,15,5,24,3,27,8,34,16,20 }`
`Returns: 85`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1961

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4706&pm=1961

vorthys

#### Testers:

zoidal , lbackstrom , schveiguy

Simulation