매출 하락 최소화

• 트리에서의 DP를 이용하는 문제.
• 사실 내가 푼 아래 코드와 공식 풀이가 거의 일치한다. 그래서 풀이는 생략.
• DP table을 명시적으로 만드는 대신 functools.lru_cache를 붙이는 것으로 처리했다.

"""Solution code for "Programmers 72416. 매출 하락 최소화".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72416
- Solution link: http://www.teferi.net/ps/problems/programmers/72416
"""

import functools


def solution(sales, links):

    @functools.lru_cache(maxsize=None)
    def min_sales(node, should_include_root):
        children_sum = sum(min_sales(c, False) for c in children[node])
        sales_including_root = sales[node] + children_sum
        if should_include_root:
            return sales_including_root
        sales_without_root = children_sum + min(
            (min_sales(c, True) - min_sales(c, False) for c in children[node]),
            default=0)
        return min(sales_including_root, sales_without_root)

    children = [[] for _ in sales]
    for a, b in links:
        children[a - 1].append(b - 1)
    return min_sales(0, False)