한 정점에서 다른 정점을 호출할 때 넘겨주는 p는 그쪽에서의 최댓값이 아닐 수 있습니다. 이쪽 편의 모든 정점을 탐색하고 얻은 결과가 아닐 수 있기 때문입니다.

자식 서브트리 내에서도 다시금 최대값을 설정하기 때문에 "부모 노드가 속한 서브 트리"와 현재 방문 노드의 최대값을 설정한다고 생각햇는데.. 다른건가요 ??

폰이라서 설명하기가 좀 어렵네요. 대신에 여기 https://ideone.com/XfVUqn 반례를 보고 원인을 생각해보세요. 정답은 4입니다.

@djm03178

아 그렇군요 감사합니다.. 제가 생각이 짧았군요.. 다시 도전해봐야겠습니다

감사합니다 !

@djm03178 저 입력의 답이 왜 4인지 모르겠습니다.

1을 없애면 (2,3,4)와 (5)가 남아 매출은 1+2 = 3

2를 없애면 (1,5), (3), (4)가 남아 매출은 1+1+1 = 3

3을 없애면 (1,2,4,5)가 남아 매출은 1

4를 없애거나 5를 없애도 매출은 1

이 되어 답은 3이라고 생각했습니다.

"매출은 알고리즘 나라에 필요한 최소한의 정비 기기의 가격의 합이다."라는 게, "각 연결 요소마다 정비 기기의 최소 가격이 가장 낮은 정점의 가격을 구하고, 그들을 합한 값"이 맞나요?

이 문제를 푼지 오래되어 생각한 게 맞는지는 모르겠는데, 아마 2를 없앴을 때 1, 5 중에 원하는 것을 선택할 수 있다는 게 아니었나 싶습니다. 그렇게 계산하면 2+1+1=4가 됩니다.

각 연결 요소에 정비 기기가 하나만 있어도 되고, 내가 정비 기기 회사의 입장에서 최대의 이윤을 내도록 배치를 한다는 게 아니었나 기억합니다.

다시 읽어 보니 "각 도시는 정비에 필요한 정비 기기의 최소 가격이 있다."라는 게 "이 도시를 정비하려면 최소 이 가격의 정비 기기가 있어야 한다."인 것 같습니다. 그렇게 해석하면 각 연결 요소마다 최대 가격을 구해서 합하는 게 되고 그러면 4가 나오네요. 문제 설명이 많이 다듬어져야 할 것 같습니다.