Untitled

from collections import defaultdict
import sys

sys.setrecursionlimit(300000)

def solution(sales, links):
    tree = defaultdict(list)
    n = len(sales)
    dp = [[-1, -1] for _ in range(n + 1)]  # dp 배열을 -1로 초기화하여 방문 여부 확인

    for a, b in links:
        tree[a].append(b)  # 방향 그래프 생성

    def dfs(node, pick):
        if dp[node][pick] != -1:
            return dp[node][pick]

        if pick:
            dp[node][1] = sales[node - 1]
        else:
            dp[node][0] = 0

        cur_m = sys.maxsize
        for nxt in tree[node]:
            if pick:
                dp[node][1] += min(dfs(nxt, True), dfs(nxt, False))
            else:
                dp[node][0] +=  dfs(nxt, False)
                cur_m = min(cur_m, dfs(nxt, True) - dfs(nxt, False))

        if not pick and cur_m < sys.maxsize:
            dp[node][0] += cur_m

        return dp[node][pick]

    res1 = dfs(1, False)
    res2 = dfs(1, True)
    
    return min(res1, res2)