1694

Jul 29, 22

Editorial

D

문제 요약:

트리가 주어진다. 모든 노드에 주어진 범위 내의 값($l_i$ ~ $r_i$)을 할당해야 한다.

한 번의 operation은 어떤 노드를 선택해 루트에서 그 노드까지 (중간에 있는 노드들을 포함할 필요 없음) 경로에 있는 노드들을 선택해 ascending 하게 0 이상의 수들을 할당하는 것이다.

조건에 맞게 트리의 노드에 값을 할당하기 위한 operation의 최솟값을 구하라.

문제 해설:

어떤 노드를 마지막으로 가지는 operation을 어떤 노드에 operation을 한다고 표현하자.

일단 어떤 노드에 operation을 할 때는 제일 큰 수를 한다. 왜냐하면 조상의 $r_i$가 더 큰 경우만 고려하면 되기 때문이다. 넘치는 경우는 고려하지 않아도 되는데, 그 이유는 넘치면 그냥 그만큼 줄여 버리면 그만이기 때문이다.

operation을 언제 해야만 할까? 자기 자식들에 operation을 했을 때 부족한 경우에는 하지 않고 만족시킬 방법이 없으므로 해야 한다.

자기 자식들에 할당할 수 있는 제일 큰 수를 할당했음에도 모자라면 그 노드에 operation이 추가적으로 필요한 것이다.

그리고 문제의 조건에 따라 어떤 노드 i에 할당할 수 있는 가장 큰 수는 당연하게도 $Min( r_i , \Sigma 자식노드에 할당된 수 )$이다.

리뷰:

이 문제를 풀 때 왜 솔루션을 못 떠올렸는지 생각을 해 봤는데, 처음에 했던 생각 자체(어떤 노드에 operation할 때 가능한 크게 하고, 위에서 할 필요가 있을 때는 모자랄 때 뿐) 은 해답과 정확히 일치한다. 그런데 내 생각이 맞는지 확실하지 않았기 때문에 계속 $l_i$가 신경이 쓰였다. 사실 $l_i$는 어떤 노드에서 넘치면 그만큼 줄여 버리고, 부모 노드로 보낼 때 그걸 반영하기만 된다는 사실을 생각하지 못했던 것 같다.