Overview

This problem asks you to find the number of departments remaining after dissolving a specified department \(K\) and all departments under its umbrella in an organization represented as a tree structure.

Analysis

This problem corresponds to the operation of deleting a subtree from a rooted tree. The key observation is that the entire subtree containing the target department \(K\) must be deleted. A naive approach would be to enumerate and delete all departments contained in the target subtree beforehand, but this is not efficient when the subtree size is large.

Instead, we can efficiently count by skipping the exploration of descendants when we reach the target department \(K\) during tree traversal. This allows us to count only the remaining departments without explicitly performing the subtree deletion.

Algorithm

1. Read the number of departments \(N\), the dissolution target \(K\), and the parent information \(P_i\) from input.
2. Build a list of child nodes for each department (\(1 \leq i \leq N\)).
3. Traverse the tree using Breadth-First Search (BFS):
   • Start the search from the root (department 1).
   • If the current node is the dissolution target \(K\), skip that node and its descendants (do not add them to the search queue).
   • Otherwise, count the node and add its child nodes to the search queue (but do not add a child node if it is \(K\)).
4. Output the count of departments.

In this approach, nodes contained in the target subtree are never explored, so the remaining number of departments can be counted efficiently.

Complexity

• Time complexity: \(O(N)\)
  • Each node is processed at most once (since the subtree of the dissolution target \(K\) is skipped).
• Space complexity: \(O(N)\)
  • \(O(N)\) is needed to store the child node lists, and up to \(O(N)\) space is needed for the BFS queue.

Implementation Notes

• By pre-building the child node list, we can efficiently access child nodes.

• In the BFS queue processing, it is important to immediately skip adding child nodes when the dissolution target \(K\) is reached.

• When reading input, parent information is given for departments 2 through N, so care must be taken with index adjustment (i-2 in the code).

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    parents = list(map(int, data[2:2+n-1]))
    
    children = [[] for _ in range(n+1)]
    for i in range(2, n+1):
        p = parents[i-2]
        children[p].append(i)
    
    count = 0
    q = deque([1])
    while q:
        node = q.popleft()
        if node == k:
            continue
        count += 1
        for child in children[node]:
            if child != k:
                q.append(child)
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.