이번 문제는 DFS를 통해 해결하였다. 모든 노드에서는 1로 모여야 하므로 1이 트리의 루트가 된다. 그렇기 때문에 루트에서 DFS를 통해 내려가며 늑대가 있다면 현재 양의 수 - 늑대의 수가 0보다 클 때 해당 수를 반환하고, 0보다 작다면 0을 반환하도록 하였고, 양이 있다면 현재 양의 수에 더해주어 반환하였다. 이렇게 최종적으로 반환되는 값이 모든 양의 수가 된다.

Code

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
bridges = [[] for _ in range(n+1)]
islands = [0 for _ in range(n+1)]
for i in range(2, n+1):
    t, a, p = map(str, input().split())
    bridges[int(p)].append(i)
    if t == 'S':
        islands[i] = int(a)
    else:
        islands[i] = -int(a)
visited = [False for _ in range(n+1)]
def move_sheep(node):
    s = islands[node]
    for nxt in bridges[node]:
        s += move_sheep(nxt)
    if s < 0:
        return 0
    else:
        return s
print(move_sheep(1))