Untitled
unknown
python
a month ago
1.0 kB
2
Indexable
Never
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)
Leave a Comment