[백준][재귀][DFS] 25515.트리 노드 합의 최댓값

25515.트리 노드 합의 최댓값

 

• 내 풀이

pypy로 하면 메모리 초과
recursion제한 안두면 런타임 에러,,,🤬 (백준 문제는 이래서 싫어)

 

• dfs로 리프노드부터 각각의 합이 양수인 경우에만 위로 보냄
• 리프노드 일때와 아닐때로 나누고
  • 아닌 경우에는 재귀
• 사이클 발생하지 않도록 visited 체크

import sys
sys.setrecursionlimit(10**6)

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)

nums = list(map(int, input().split()))
visited = [False for _ in range(n)]


def dfs(cur):
    if not graph[cur]:
        visited[cur] = True
        return max(0, nums[cur])

    tmp = nums[cur]
    for nxt in graph[cur]:
        if visited[nxt]:
            continue
            
        val = dfs(nxt)
        if val <= 0:
            continue
        tmp += val

    visited[cur] = True
    return tmp

print(dfs(0))