HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50701 - Cell Removal

Guest
• Discussion of problem (1)

Section problems

• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - The traveling salesman prob...
• 50701 - Cell Removal
• 50703 - The Shortest Path
• 50704 - Connected?
• 50705 - Student Clubs

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Difficulty Beta

In biology, organisms have the following property: Starting from the first cell (the zygote), each cell during an organism's development process either divides into 2 other cells or does not divide at all. An organism is mature when all of its cells will not divide any further.

Let's assign a unique number to each cell in an organism's development process. For example, consider a species in which each organism starts with cell 0, which divides into cells 1 and 2. Cell 1 divides into cells 3 and 4. Cells 2, 3 and 4 do not divide. Every mature organism of this species will consist of exactly 3 cells - 2, 3 and 4.

During the development process, if we kill a cell, it will be absent in the mature form of the organism. If that cell happens to be a cell that divides, then the mature organism will be missing all of the cell's descendants as well because the cell is killed before it has a chance to divide. For example, in the organism described above, if we kill cell 1 during the development process, the mature organism will contain only cell 2.

You are given N cells numerated from 0 to N-1. For each cell you know the index of it's parent. The zygote's parent is -1. Return the number of cells the mature form of this organism would have if you killed cell deletedCell during the development process.

Input
The first line contains two numbers N and deletedCell (1 ≤ N ≤ 50, 0 ≤ deletedCellN-1). Next N lines will contain parents of corresponding cells. Each parent will be between -1 and N-1 inclusive. It is guaranteed, that there will be at least one line. Also it is guaranteed that this array of parents will form a binary tree without any cycles.
Output
Output single number - the number of cells the mature form of this organism would have if you kill cell deletedCell during the development process.

Input 1 Input 2 Input 3 Input 4
1 0
-1
3 0
-1
0
0
3 2
1
-1
1
7 3
5
3
6
6
3
-1
5
Output 1 Output 2 Output 3 Output 4
0
0
1
2

Для отправки решений необходимо выполнить вход.

www.contester.ru