푸는 방법이 1번 노드부터 차례대로 선택했는지 안했는지 가지고 최소값 dp하는 방법밖에 안떠오르는데

어떤 노드를 선택해왔는지에 따라서 달라져서 

이정보를 다 넘기기엔 cash값이 너무 커져서 풀수가 없네요.

어떤기가막힌 방법이 있는지 궁금합니다 ㅎ