[백준] 26972 - Barn Tree (c++)

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

 

문제 요약

트리가 주어진다. 각 정점에 건초 수가 주어진다. 건초는 인접한 정점으로 한 번에 원하는 만큼 옮길 수 있다. 건초를 옮기는 횟수를 최소로 해서 모든 정점의 건초 수가 같게 만들어라.

 

풀이 (N)

• 트리DP

각 정점의 건초 수를 평균으로 맞춰야 한다. 건초를 옮겨야 하는 정점은 정해져 있고(평균이 아닌 정점) 트리에서 경로는 유일하기 때문에 횟수는 중요한게 아니고 어떻게 옮길지만 생각하면 된다. 각 서브트리의 전체 건초 수가 정해져 있기 때문에 남는건 루트로 올리고 부족한 건 루트에서 받아오면 된다. 과정중에 건초가 -개가 되면 안되니까 올리는 과정을 먼저하고 내리는 과정을 나중에 해줘야 한다.