概要

木構造で表される組織において、指定された部署\(K\)とその傘下のすべての部署を解体した後に残る部署の数を求める問題です。

考察

この問題は、根付き木から部分木を削除する操作に対応します。重要な観察点は、解体対象の部署\(K\)を含む部分木全体を削除する必要があることです。素朴なアプローチとして、解体対象の部分木に含まれるすべての部署を事前に列挙して削除する方法が考えられますが、これでは部分木のサイズが大きい場合に効率的ではありません。

代わりに、木を走査する際に解体対象の部署\(K\)に到達したら、その子孫への探索をスキップすることで効率的にカウントできます。これにより、部分木の削除を明示的に行わずに、残る部署だけを数えることができます。

アルゴリズム

1. 入力から部署数\(N\)、解体対象\(K\)、親情報\(P_i\)を読み取ります。
2. 各部署の子ノードリストを作成します（\(1 \leq i \leq N\)）。
3. 幅優先探索（BFS）を用いて木を走査します：
   • ルート（部署1）から探索を開始します。
   • 現在のノードが解体対象\(K\)の場合は、そのノードと子孫をスキップします（探索キューに追加しません）。
   • それ以外のノードはカウントし、その子ノードを探索キューに追加します（ただし子ノードが\(K\)の場合は追加しません）。
4. カウントした部署の数を出力します。

このアプローチでは、解体対象の部分木に含まれるノードは探索されないため、効率的に残りの部署数を数えられます。

計算量

• 時間計算量: \(O(N)\)
  • 各ノードは最大1回ずつ処理されます（解体対象\(K\)の部分木はスキップされるため）。
• 空間計算量: \(O(N)\)
  • 子ノードリストの格納に\(O(N)\)、BFSのキューに最大\(O(N)\)の空間が必要です。

実装のポイント

• 子ノードリストを事前に構築することで、効率的に子ノードへアクセスできます。

• BFSのキュー処理において、解体対象\(K\)に到達したら即座に子ノードの追加をスキップすることが重要です。

• 入力の読み取り時、部署2からNまでの親情報が与えられるため、インデックス調整に注意が必要です（コード中のi-2）。

  ソースコード

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()

この解説は deepseekv3 によって生成されました。