[PS] 트리 (백준 1068번)

트리의 기본 연습 문제이다.

''' BOJ no.1068 - 트리 (트리) '''

import sys

sys.setrecursionlimit(100000)
N = int(sys.stdin.readline())
tree = [ [] for _ in range(N) ]
each_parent = [ -1 for _ in range(N) ]
count_of_leaf = 0
count_of_removed_leaf = 0
root_node = 51

def clean_of_tree():
    global root_node
    for idx, parent_node in enumerate(list(map(int, sys.stdin.readline().split()))):
        if parent_node == -1:
            root_node = idx
            continue
        each_parent[idx] = parent_node
        tree[parent_node].append(idx)

def dfs(node_number):
    global count_of_removed_leaf
    if len(tree[node_number]) == 0:
        count_of_removed_leaf += 1
        return

    for node_number in tree[node_number]:
        dfs(node_number)

def process():
    global count_of_leaf, root_node
    removed_node = int(sys.stdin.readline())

    if each_parent[removed_node] == -1:
        print(0)
        return

    # Parent Node의 자식 중 제거할 노드를 제외시킴.
    tree[each_parent[removed_node]].remove(removed_node)

    # leaf node 세기 (for dfs)
    dfs(root_node)

    print(count_of_removed_leaf)

if __name__ == '__main__':
    # 트리 정리
    clean_of_tree()
    process()