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 ≤ deletedCell ≤ N-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
|
Для отправки решений необходимо выполнить вход.
|