Overview

This problem asks you to find the number of remaining departments after deleting a specified department and all its subordinates (subtree) from an organizational chart represented as a tree structure.

Analysis

Essence of the Problem

This problem can be reduced to “finding the size of the subtree rooted at a given vertex” in a tree structure.

Dismantling department \(K\) and all its subordinates means deleting all vertices contained in the subtree rooted at department \(K\). Therefore, the answer can be computed as follows:

\[\text{Number of remaining departments} = N - \text{(Size of the subtree rooted at department } K\text{)}\]

Understanding with a Concrete Example

For example, consider the following organizational chart (\(N = 5\), \(K = 2\)):

    1 (Headquarters)
   / \
  2   3
 / \
4   5

When department \(2\) is dismantled, its subordinate departments \(4, 5\) are also dismantled together. - Dismantled departments: \(2, 4, 5\) (3 departments) - Remaining departments: \(1, 3\) (2 departments)

Therefore, the answer is \(5 - 3 = 2\).

Why a Simple Approach Works

This problem has the constraint \(N \leq 2 \times 10^5\). Since it suffices to visit each vertex exactly once to find the subtree size, a simple \(O(N)\) traversal solves the problem without any issues.

Algorithm

1. Build the tree structure: For each department, create a list of its child departments (children).

2. Compute the subtree size using BFS (Breadth-First Search):

   • Start from department \(K\)
   • Use a queue to visit all departments under \(K\) (including \(K\) itself) in order
   • Count the number of visited departments

3. Compute the answer: The answer is \(N\) minus the subtree size.

You can also solve this similarly using DFS (Depth-First Search) instead of BFS.

BFS flow (when K=2):
Queue: [2] → Count: 1
Queue: [4, 5] → Count: 2
Queue: [5] → Count: 3
Queue: [] → Done

Complexity

• Time complexity: \(O(N)\)

  • \(O(N)\) for building the tree structure
  • \(O(N)\) since BFS/DFS visits each vertex at most once

• Space complexity: \(O(N)\)

  • \(O(N)\) for storing the children list (children)
  • The BFS queue may contain up to \(O(N)\) elements

Implementation Notes

1. Input handling: Since \(P_i\) represents the parent of department \(i\) (\(2 \leq i \leq N\)), careful attention to indexing is needed. P_values[i-2] is the parent of department \(i\).

2. Special handling when \(N = 1\): When \(N = 1\), the input line for \(P\) may be empty or nonexistent, so we handle this case separately first. In this case, the number of remaining departments after dismantling is 0.

3. Using deque: In Python, removing from the front of a list costs \(O(N)\), but using collections.deque allows this in \(O(1)\). This is important for implementing BFS efficiently.

   Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    
    if N == 1:
        # N=1の場合、P の入力行がない可能性がある
        print(0)
        return
    
    P = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    
    P_values = list(map(int, input().split()))
    for i in range(2, N + 1):
        P[i] = P_values[i - 2]
        children[P[i]].append(i)
    
    # BFSで部署Kとその傘下の部署の数を数える
    count = 0
    queue = deque([K])
    while queue:
        node = queue.popleft()
        count += 1
        for child in children[node]:
            queue.append(child)
    
    print(N - count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.