概要

木構造で表された組織図から、指定された部署とその傘下（部分木）をすべて削除したとき、残る部署の数を求める問題です。

考察

問題の本質

この問題は、木構造において「ある頂点を根とする部分木のサイズを求める」問題に帰着できます。

部署 \(K\) とその傘下をすべて解体するということは、部署 \(K\) を根とする部分木に含まれるすべての頂点を削除することを意味します。したがって、答えは以下のように求められます：

\[\text{残る部署の数} = N - \text{（部署 } K \text{ を根とする部分木のサイズ）}\]

具体例で理解する

例えば、以下のような組織図を考えます（\(N = 5\), \(K = 2\)）：

    1 (本社)
   / \
  2   3
 / \
4   5

部署 \(2\) を解体すると、その傘下の部署 \(4, 5\) も一緒に解体されます。 - 解体される部署：\(2, 4, 5\)（3個） - 残る部署：\(1, 3\)（2個）

よって答えは \(5 - 3 = 2\) となります。

なぜ単純な方法でOKか

この問題では \(N \leq 2 \times 10^5\) という制約があります。部分木のサイズを求めるために全頂点を1回ずつ見れば十分なので、\(O(N)\) の単純な探索で問題なく解けます。

アルゴリズム

1. 木構造の構築: 各部署について、その子部署のリスト（children）を作成します。

2. BFS（幅優先探索）で部分木のサイズを計算:

   • 部署 \(K\) からスタート
   • キューを使って、\(K\) とその傘下のすべての部署を順に訪問
   • 訪問した部署の数をカウント

3. 答えの計算: \(N\) から部分木のサイズを引いた値が答えです。

BFSの代わりにDFS（深さ優先探索）を使っても同様に解けます。

BFSの流れ（K=2の場合）:
キュー: [2] → カウント: 1
キュー: [4, 5] → カウント: 2
キュー: [5] → カウント: 3
キュー: [] → 終了

計算量

• 時間計算量: \(O(N)\)

  • 木構造の構築に \(O(N)\)
  • BFS/DFSで各頂点を最大1回ずつ訪問するので \(O(N)\)

• 空間計算量: \(O(N)\)

  • 子リスト（children）の格納に \(O(N)\)
  • BFSのキューに最大 \(O(N)\) 個の要素が入る可能性がある

実装のポイント

1. 入力の処理: \(P_i\) は部署 \(i\)（\(2 \leq i \leq N\)）の親を表すので、インデックスに注意が必要です。P_values[i-2] が部署 \(i\) の親になります。

2. \(N = 1\) の場合の特別処理: \(N = 1\) のとき、\(P\) の入力行が空または存在しない可能性があるため、先に場合分けしています。この場合、解体後に残る部署は0個です。

3. dequeの使用: Pythonでは、リストの先頭からの削除は \(O(N)\) かかりますが、collections.deque を使うと \(O(1)\) で行えます。BFSを効率的に実装するために重要です。

   ソースコード

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

---

この解説は claude4.5opus によって生成されました。