Directory Deletion
Binary tree
Data structures
Depth first search
Easy
Trees
62.0% success
13,773 attempts
2s time
256MB memory
1024KB max code

You are given a directory tree of \(N\) directories/folders. Each directory is represented by a particular \(id\) which ranges from \(1\) to \(N\). The id of the root directory is \(1\), then it has some child directories, those directories may contain some other ones and it goes on. Now you are given a list of directory id's to delete, you need to find the minimum number of directories that need to be deleted so that all the directories in the given list get deleted. 

Note that if you delete a particular directory, all its child directories will also get deleted.

Input
The first line of input contains an integer \(N\) that denotes how many folders are there.
The next line contains \(N\) space separated integers that where the \(i^{th}\) integer denotes the id of the parent of the directory with id \(i\) . Note that the first integer will be \(-1\) as \(1\) is the id of root folder and it has no parent. Rest of the integers will not be \(-1\) .
The next line contains an integer \(M\) that denotes how many directories you need to delete.
The next line contains \(M\) space separated integers that denote the ids of the directories you need to delete.

Output
Print the minimum number of directories that need to be deleted.

Constraints
\(1 \le N \le 10^5 \)
\(1 \le id \ of \ parent \le N \)
\(1 \le M \le N \)
\(1 \le id \ to \ be \ deleted \le N\)

Examples
Input
7
-1 1 1 3 3 4 4
3
2 3 4
Output
2
Explanation

In the image below is the complete directory tree. If you delete the directories 2 and 3, 4 gets automatically deleted, thus you need to delete only 2 directories. 

This image is generated in csacademy graph editor
Designed in Csacademy graph creator

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Directory Deletion | Binary/ N-ary Trees & Data Structures Practice Problems