C - Dissolution of the Department Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は大企業の組織管理を担当しています。この会社には N 個の部署があり、各部署には 1 から N までの番号が付けられています。番号 1 は会社全体を統括する本社です。

会社の組織構造は根付き木として表されており、番号 1 の本社が根です。番号 i（2 \leq i \leq N）の部署の親は番号 P_i の部署です。すなわち、番号 i の部署は番号 P_i の部署の直属の下部組織です。

ある日、経営陣は組織のスリム化を図るため、番号 K の部署を解体することを決定しました。解体では、番号 K の部署自身と、その子孫にあたるすべての部署が取り除かれます。ここで、番号 K の部署の子孫とは、根付き木において番号 K の部署の子、子の子、…と再帰的にたどれるすべての部署を指します（番号 K の部署自身は子孫には含みません）。

解体後に会社に残る部署の数を求めてください。K = 1 の場合は会社の全部署が解体の対象となるため、答えが 0 になることに注意してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq P_i < i（2 \leq i \leq N）
  • 入力はすべて整数である

入力

N K
P_2 P_3 \cdots P_N
  • 1 行目には、部署の総数 N と、解体の起点となる部署の番号 K が、スペース区切りで与えられる。
  • 2 行目には、番号 2 から N までの各部署の親の番号 P_2, P_3, \ldots, P_N が、スペース区切りで与えられる。ただし N = 1 のときは 2 行目は存在せず、入力は 1 行のみである。

出力

番号 K の部署とその子孫にあたるすべての部署を解体した後に残る部署の数を 1 行で出力してください。

入力例 1

5 3
1 1 3 3

出力例 1

2

入力例 2

8 2
1 1 2 2 3 5 5

出力例 2

3

入力例 3

15 4
1 1 2 2 3 3 4 4 5 6 7 8 9 9

出力例 3

9

Score : 366 pts

Problem Statement

Takahashi is in charge of organizational management at a large company. The company has N departments, each numbered from 1 to N. Department 1 is the headquarters that oversees the entire company.

The company's organizational structure is represented as a rooted tree, with department 1 (headquarters) as the root. The parent of department i (2 \leq i \leq N) is department P_i. In other words, department i is a direct subdivision of department P_i.

One day, the management decided to dismantle department K in order to streamline the organization. The dismantling removes department K itself and all departments that are its descendants. Here, the descendants of department K refer to all departments that can be reached by recursively following children of department K in the rooted tree — that is, children, children of children, and so on (department K itself is not included in its descendants).

Determine the number of departments remaining in the company after the dismantling. Note that if K = 1, all departments in the company are subject to dismantling, so the answer is 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq P_i < i (2 \leq i \leq N)
  • All input values are integers.

Input

N K
P_2 P_3 \cdots P_N
  • The first line contains the total number of departments N and the number K of the department to be dismantled, separated by a space.
  • The second line contains the parent numbers P_2, P_3, \ldots, P_N for departments 2 through N, separated by spaces. However, when N = 1, the second line does not exist and the input consists of only one line.

Output

Print on one line the number of departments remaining after dismantling department K and all of its descendant departments.

Sample Input 1

5 3
1 1 3 3

Sample Output 1

2

Sample Input 2

8 2
1 1 2 2 3 5 5

Sample Output 2

3

Sample Input 3

15 4
1 1 2 2 3 3 4 4 5 6 7 8 9 9

Sample Output 3

9