All Tracks Data Structures Trees Binary/ N-ary Trees Problem

Directory Deletion
/

Binary/ N-ary Trees, Data Structures, Depth-first search, Tree

Problem
Editorial
Analytics

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\)

SAMPLE INPUT
7
-1 1 1 3 3 4 4
3
2 3 4
SAMPLE 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

 

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?