Overview

This problem requires finding the size of the subtree rooted at a specific vertex (department) \(K\) in a tree structure (organizational chart), and subtracting it from the total number of vertices \(N\).

Analysis

Problem Breakdown

• The entire company is a tree structure consisting of \(N\) departments.
• Department \(1\) is the root (headquarters).
• When department \(K\) is dissolved, department \(K\) itself and all departments under it (children, grandchildren, …) are eliminated.
• What we want to find is “the number of remaining departments”, i.e., \(N - (\text{size of the subtree rooted at department } K)\).

How to Find the Subtree Size

Typically, to find the size of a subtree in a tree structure, a common approach is to use depth-first search (DFS) or similar methods to count from the leaves upward. However, this problem has a very important constraint:

\(1 \leq P_i < i\) （ \(2 \leq i \leq N\) ）

This constraint means that “a parent’s number is always smaller than its child’s number”. In other words, if we process departments in decreasing order of their numbers, by the time we process department \(i\), the sizes of all its child departments (those with numbers greater than \(i\)) are guaranteed to have already been computed.

By leveraging this property, we can compute subtree sizes with a simple loop, without needing to implement complex graph traversals (DFS or BFS).

Algorithm

Using an approach similar to dynamic programming (DP), we solve the problem with the following steps:

1. Initialization: Prepare an array subtree_size to hold the subtree size of each department \(i\), and initialize all values to \(1\) (counting the department itself).
2. Bottom-up aggregation: Loop through department numbers \(i\) from \(N\) down to \(2\) in reverse order.
   • Let \(P_i\) be the parent of department \(i\). Add subtree_size[i] to subtree_size[P_i].
   • By processing in decreasing order of numbers, we ensure that each child’s size is finalized before adding it to the parent.
3. Computing the answer: Output the value obtained by subtracting the subtree size of the target department \(K\), subtree_size[K], from the total count \(N\).

Complexity

• Time complexity: \(O(N)\) Since we traverse from department \(N\) to \(2\) exactly once, the computation finishes in linear time with respect to the number of vertices \(N\).
• Space complexity: \(O(N)\) We use \(O(N)\) memory for the array storing parent information and the array storing subtree sizes.

Implementation Notes

• Speeding up input: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is efficient to read all input at once using methods like sys.stdin.read().split().

• Index adjustment: The problem gives parent information \(P_i\) sequentially for departments \(2, 3, \ldots, N\). When stored in a list P_list, note that the parent of department \(i\) is accessed as P_list[i-2].

• Reverse loop: By using range(N, 1, -1), we can propagate sizes from department \(N\) upward to parents. This also eliminates any concern about stack overflow from recursive function calls.

  Source Code

import sys

def solve():
    # 競技プログラミングにおいて、大量の入力を高速に読み込むために sys.stdin.read を使用します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 部署の総数, K: 解体する部署の番号
    N = int(input_data[0])
    K = int(input_data[1])
    
    # P_list は番号 2 から N までの各部署の直属の上位部署のリストです
    # P_list[0] が P_2, P_list[N-2] が P_N に対応します
    if N > 1:
        P_list = list(map(int, input_data[2:]))
    else:
        P_list = []
        
    # subtree_size[i] は部署 i を根とする部分木に含まれる部署の数を保持します
    # 最初は自分自身のみをカウントするため、すべて 1 で初期化します
    subtree_size = [1] * (N + 1)
    
    # 制約 P_i < i により、番号が大きい部署から順に処理することで、
    # ある部署を処理する際には、その部署のすべての子（下部組織）のサイズが計算済みであることが保証されます
    # 番号 N から 2 まで逆順にループを回します
    for i in range(N, 1, -1):
        # 部署 i の親（上位部署）の番号を取得
        # P_list は 0-indexed なので、部署 i の親は P_list[i-2] に格納されています
        parent = P_list[i-2]
        # 親の subtree_size に、現在の部署 i の subtree_size を加算します
        subtree_size[parent] += subtree_size[i]
        
    # 全体の部署数 N から、解体対象の部署 K とその傘下の部署の総数（subtree_size[K]）を引きます
    ans = N - subtree_size[K]
    
    # 結果を出力します
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.