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

Directory Deletion
Tag(s):

Binary/ N-ary Trees, Data Structures, Depth-first search, Easy, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Wissen Technology Pvt ltd

Challenge Name

Wissen Software Developer Hiring Challenge.

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?