경로 조정하기

아래 보인 이진 트리에서 루트 노드로부터 각 잎 노드(최하위의, 자식이 없는 노드들)까지 경로의 길이는 다양하다. 경로의 길이는 경로 상에 있는 간선(들)의 가중치의 합으로 정의한다.

일부 간선의 가중치를 증가시켜 루트 노드로부터 모든 잎 노드까지의 경로 길이를 같게 만들고자 한다. 단, 증가시키는 가중치의 합이 최소가 되도록 하길 원할 때, 증가시키는 가중치(최종 가중치 - 원래 가중치)의 합은 얼마인가?

문제 형식

주관식

출처

• KOI 2021 1차대회 중등부 1교시 7번