Overview

Given a department structure represented as a tree, we need to find the number of departments remaining after deleting the subtree rooted at a specified department \(K\) (i.e., \(K\) and all its subordinates).

Analysis

What gets deleted in this problem is “all vertices contained in the subtree of department \(K\).” Therefore, we can reduce the problem to:

• Remaining departments = Total departments \(N\) − (subtree size of \(K\))

The key is to correctly count the “subtree size of \(K\).” Since the input gives the parent \(P_i\) for each vertex \(i(2 \le i \le N)\), we first build an adjacency list from parent to children (child list), then we can count the subtree size by traversing downward from \(K\) using DFS/BFS.

A naive approach of “checking whether each vertex is a subordinate of \(K\)” by tracing parents upward would take \(O(N)\) per vertex in the worst case (going all the way to the root), resulting in \(O(N^2)\) overall, which is too slow for \(N \le 2 \times 10^5\).
Instead, we build the child list and perform a single traversal from \(K\), counting only the vertices within the subtree in \(O(\text{subtree size})\).

Example:
If the subtree of \(K=3\) contains 5 vertices, then \(N-5\) departments remain after deletion.

Algorithm

1. Using the parent array \(P_2,\dots,P_N\) from the input, build an array children that lists the children of each vertex.
   
   • Add child i to children[p] (imagine creating the edge \(p \to i\)).
2. Prepare a stack (or queue), push \(K\), and start the traversal (iterative DFS).
3. Each time a vertex \(v\) is popped from the stack, increment the count by 1 and push all children in children[v] onto the stack.
4. The count sub obtained from the traversal is the subtree size, so the answer is \(N - sub\).

Complexity

• Time complexity: \(O(N)\)
  (Building the child list is \(O(N)\), and the traversal processes each vertex at most once)
• Space complexity: \(O(N)\)
  (For the child list and the stack)

Implementation Notes

• Recursive DFS can reach a depth of up to \(N\), which may hit Python’s recursion limit. The code safely uses iterative DFS with a stack instead.

• Since \(P\) starts from \(P_2\), note that the parent of vertex i is P[i-2].

• When \(N=1\), the line containing parent information is empty, so P is handled as an empty array.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    P = list(map(int, input().split())) if N >= 2 else []

    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        p = P[i - 2]
        children[p].append(i)

    stack = [K]
    sub = 0
    while stack:
        v = stack.pop()
        sub += 1
        stack.extend(children[v])

    print(N - sub)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.