[백준/C++] 13325번: 이진 트리

문제

https://www.acmicpc.net/problem/13325

---

문제 요약

각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다.

 

루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다.

 

에지들의 가중치를 증가시켜 루트에서 모든 리프까지의 거리가 같도록 하고,

에지 가중치들의 총합을 최소화해야 한다.

---

코드

???

---

코드 설명

그래프의 높이는 0부터 k까지 존재한다.

그래프의 노드는 1번부터 2^(k+1) - 1번까지 존재하고, 간선은 총 2^(k+1) - 2개가 존재한다.

 

i / 2번 노드에서 i번으로 이어진 간선의 가중치를 edges[i]에 저장한다.

 

dfs 함수는 재귀적으로 트리를 후위 순회하며 i번 노드에서 리프까지 거리의 최대값을 반환한다.

 

dfs 함수는 다음과 같이 동작한다.

 

1. 리프 노드일 경우, 0을 반환한다.

2. i에서 왼쪽/오른쪽 자식까지 거리 + i의 왼쪽/오른쪽 자식부터 리프까지 최대 거리를 계산한다.

   => i번 노드에서 리프까지 거리의 최대값을 계산한다. (재귀 이용)

3. 두 거리의 차이를 계산하고 더 큰 값에 맞춰, i에서 작은쪽 자식까지의 가중치를 수정한다.

 

마지막으로 모든 수정된 에지의 합을 계산한다.