質問リンク

問題の説明

に答える

コード#コード#

import sys
from collections import deque

def solution():
    read = sys.stdin.readline
    n = int(read())
    parents = list(map(int, read().split()))
    to_delete = int(read())

    # 루트를 삭제하면
    if parents[to_delete] == -1:
        print(0)
        return

    root = -1
    adj_list = [[] for _ in range(n)]
    for child in range(n):
        if child == to_delete:
            continue
        parent = parents[child]
        if parent == -1:
            root = child
            continue
        adj_list[parent].append(child)

    print(bfs(root, adj_list))

def bfs(root, adj_list):
    count = 0
    q = deque([root])
    while q:
        parent = q.popleft()
        if not adj_list[parent]:
            count +=1
        for child in adj_list[parent]:
            q.append(child)
    return count

solution()