매출 하락 최소화

import sys; sys.setrecursionlimit(1000001) from collections import defaultdict from math import inf cost = None # DP cache # u가 팀장이면 # A[u]: 팀장 u를 반드시 선택하여 만들 수 있는 하위 subtree 매출액 하락의 최솟값 # B[u]: 팀장 u를 선택하지 않고 만들 수 있는 하위 subtree 매출액 하락의 최솟값 # u가 팀장이 아니면 # A[u]: u의 cost # B[u]: 0 A, B = {}, {} # 점화식 # A[u] = sum( min(A[v], B[v]) for v in u.children ) + u.cost # B[u] = ("적어도 하나는 A[v]가 선택된 상태"라는 조건) sum( min(A[v], B[v]) for v in u.children ) # base case # u의 팀이 말단 팀일 경우 # A[u] = u.cost # B[u] = min(v.cost for v in u.children) def solve(u, Adj, T): # u가 팀장이 아니면 if u not in Adj: A[u] = cost[u-1] B[u] = 0 # 팀장 u가 이미 처리된 상태면 바로 리턴 if u in A: return # u의 팀이 말단 팀일 경우 if u not in T: A[u] = cost[u-1] B[u] = min(cost[v-1] for v in Adj[u]) return for v in Adj[u]: solve(v, Adj, T) A[u] = sum( min(A[v], B[v]) for v in Adj[u] ) + cost[u-1] # B는 "각 v에 대해 A[v]가 반드시 선택된 경우"마다 # 경우의 수를 나누어 처리합니다. mn = inf for v in Adj[u]: tmp = 0 for x in Adj[u]: if x == v: tmp += A[v] else: tmp += min(A[x], B[x]) mn = min(tmp, mn) B[u] = mn def solution(sales, links): global cost cost = sales links.sort() # Adjacency list를 만듭니다. Adj = defaultdict(list) for u, v in links: Adj[u].append(v) # 각 팀의 팀장을 바로 알 수 있도록 합니다. # 1을 제외하고는, set의 크기가 2인 엔트리들이 팀장들입니다. leader = defaultdict(set) for u, v in links: leader[v].add(u) leader[u].add(u) T = defaultdict(list) # 각 팀간의 연결관계를 유추합니다. for u, l in leader.items(): if len(l) == 1: continue for x in l: if x == u: continue T[x].append(u) solve(1, Adj, T) return min(A[1], B[1])