Directory Deletion
Practice
3.3 (23 votes)
Binary tree
Data structures
Depth first search
Easy
Trees
Problem
58% Success 11623 Attempts 20 Points 2s Time Limit 256MB Memory 1024 KB 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\)

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...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
2 votes
Tags:
Prime FactorizationLCMMedium-HardMathematicsFactorization
Points:20
82 votes
Tags:
EasyTrees
Points:20
57 votes
Tags:
Binary TreeData StructuresDepth First SearchEasyHash MapsTrees